A Topology-aware Graph Coarsening Framework for Continual Graph Learning
Authors: Xiaoxue Han
Zhuo Feng
Yue Ning
Venue: NeurIPS 2024 poster (2024)
Keywords: Continual Graph Learning
Catastrophic Forgetting
Graph Coarsening
Primary area: graph_neural_networks

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.

A Topology-aware Graph Coarsening Framework for Continual Graph Learning
Xiaoxue Han Stevens Institute of Technology xhan260stevens. edu
Zhuo Feng Stevens Institute of Technology 2f www.nnnsteeeess.co
Yue Ning
Stevens Institute of Technology
yue. ning@stevens edu
Abstract
Graph Neural Networks (GNNs) experience "catastrophic forgetting" in contin- ual learning setups, where they tend to lose previously acquired knowledge and perform poorly on old tasks. Rehearsal-based methods, which consolidate old knowledge with replay memory buffer, are de facto solution due their straightforward workflow. However, these methods often fail to adequately cap- ture topological information, leading 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 reduced graph. Throughout each learning period, this reduced graph ex- pands by integrating with new graph and aligming shared nodes, followed by "zoom-out" reduction process to maintain stable size. We have developed graph coarsening algorithm based on node representation proximities effi- ciently reduce 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 CO with wide range of state-of-the-art baselines, proving its superiority and the necessity of preserving high-quality topological information for effective replaying. Our code is available at: /tctps://githul com wom./hanxiaaxxee1//Ae..
Introduction
Graph neural networks (GNNs) are oblivious: they fail consider 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 (also known incremental learning lifelong learning) setup, [3 20
39 the
model learns a sequence of tasks incrementally, where each task defined as learning session on subgraph. This problem becomes more intractable as the model has no access to previous data, resulting in drastic degradation of model performance on old tasks. To tackle the issue of "catastrophic forgetling" " in GNNs, several approaches have been proposed. Among them, rehearsal- based methods [18 57 48 55 are the most common due to their straightforward workflow and efficacy in consolidating old knowledge with affordable additional memory. When performing node classification tasks, these methods utilize memory buffers to save node samples during the rehearsal process of online graph training. However, they often fail adequately capture topological information which important in downstream tasks. As demonstrated by Zügner et al. [58], even small changes in edges can alter the expected node labels, causing the model to learn incorrect imput
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(feature, structure)-label mappings from the replay samples which creates vulnerability and security issues in critical domains 42)
To address this, we propose a dynamic graph coarsening framework, TACO, that efficiently preserves high-quality topology information for experience replay. TACO operates through a straightforward yet effective workflow: At the end of each training task, it reduces the current graph into a compressed form that maximally preserves its properties, allowing to serve as proxy for the original graph; for the next task, the reduced graph and the new graph are combined by aligning co-existing nodes, and the model is trained on this new combined graph. The former step preserves information from the intra-tast task edges (edges connecting nodes from the same task), while the latter step allows us to retrieve the inter-task (edges connecting nodes from different tasks) ones. Noticing that most existing graph reduction algorithms focus solely on preserving graph topology properties and are often inefficient, we propose an efficient graph reduction algorithm, RePro, as component of the CGL. framework. RePro leverages the proximities between learned node representations to effectively preserve node features and spectral properties during the reduction process. 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. We claim that the simplicity of TACO makes it highly modular and adaptable. We conduct extensive experiments and perform comprehensive ablation studies to evaluate the effectiveness of TO and RePro. We also compare our method with multiple state-of- the-art methods [2 26 graph coarsening tasks.
30 55) for both CGL and
2 Preliminaries
2.1 Setup explanations
We notice that most existing research CGL 26 57 55
focuses either lusk-incremental-
learning (task-IL) [45] or a tranductive [54] 3 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, there are 10 classes in total, and this experimental setting divides these classes into 5 tasks. Task focuses classifying classes 1 and 2, while task 2 classifies classes 3 and 4, and so on. Since GNNs often forget knowledge of old classes and show trivial performance, the improvement of the CGL framework be easily highlighted with large margins. However, we argue that this setting may not accurately simulate real-life scenarios.
In this paper, we aim to tackle a more realistic inductive and Generalized Mlus-inncrementalleaaraaa (generalized class-IL) [32] setting. In real-world graphs, nodes and edges often associated with time stamp indicating their appearing time, and graphs keep expanding with new nodes and edges. For instance, in citation network, each node representing paper cites (forms 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 in- crementally and dynamically because saving or retraining the model on the full graph can be pro-
Percentage each class
100
hibitively expensive in space and time. So we
Porcentage (86)
Triining tack
62.8
96.8
split streaming graph into subgraphs based time periods and train a model on each subgraph sequentially for the node classification task. In
56.0
14.6
96.1
50
62.1
87.0
64.8 58.9
88.8
such cases, subgraphs are correlated with each other through the edges connecting them (e.g. paper cites another paper from previous time stamps). The structural information represented by edges may change from previous tasks (in- ductive). Also, since the tasks are divided by time periods instead of class labels, there are overlapping classes between new tasks and old tasks, so the model needs to perform classification across all classes (generalized class-IL).
1
2
3
4
5
Task
Test task
(a) Class distribution
(b) Fl score
Figure I: Class distributions in the Kindle dataset change over time and the model trained new tasks tends to forget old 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 [3] 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 gradual shift of node class distribution over time, as shown in Figure [.). Furthermore, even for nodes the same class, their features and neighborhood patterns can shift [18.. 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 exacerbates the forgetting problem. The Fl scores of node classification tasks using Graph Convolutional Network (GCN) [19] show that the model performs significantly worse on previous tasks when trained Although this paper focuses on generalized class-IL setting, we also conduct experiments on data splits with traditional class-IL setting to prove the generalizability of TACO.
ones without strategies alleviate forgetting, shown in Figure (b). Tig
2.2 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 trained for sequential node classification tasks with no access to previous training data, but it can utilize a memory buffer with 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 graph. For each task, the GNN model is trained on subgraph where source nodes belonging to a specified time period, and all tasks are ordered 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 life scenarios. We formulate the above problems as follows.
Problem 1. Continual learning on time-stamped graphs. We are given time sime-stamped expanding graph G = (V. ",E,A,X,, A,X,Y) Y), where V denotes the node set, & denotes the edge set, A E RIV x|V] and X E R xdx denote the adjacency matrix and node features, respectively; Y is one-hot embedding matrix denoting class labels. Each node V is assigned time period 7(v). We define a sequence of subgraphs, G1...., Gk. such that each subgraph G. = (Ve, E,, A,, X₂) from G is formulated based on the following rules:
For edges in Gj: e= (s,o) E & E and T())= 14 For nodes in G.: u V. + r()) = to ((s,0) E E and T(s) = t).
where 8 is source node and o (or v) is a target node. We can assume r(o) T(s) for (s, E (e.g. in citation network, a paper can not cite another paper published in the future). The nodes on each subgraph Gr, are divided into three sets for training, validation, and test. We implement GNN to perform node classification tasks and sequentially train the model on I..... Gg. When the model is trained with a new task Tú, it has no access to G...., Gi-1 and Ge+1,..., 9.. However, a small memory buffer is allowed to preserve useful information from previous tasks. The objective to optimize the overall performance of the model on test nodes from all tasks when the model incrementally trained with new tasks.
Problem 2. Graph coarsening. Given graph 9 (V,E) with |V] nodes, the goal of graph
coarsening is to reduce to a target size n' with a specific ratio where n'' = 17 n2.0 < < < 1. We construct the coarsened graph G (V*,, (T)) through partitioning to n'' disjoint clusters (CI,..,, ), ), so that each cluster becomes a node in Gr. The construction of these clusters (i.c., the partition of graph) depends on coarsening strategies. The node partitioning/clusteiigg information can be represented by a matrix Q E Buxn', If we assign every node in cluster C with the same weight, then Qú, = 1; If node i is not assigned to cluster Cj. Qij = O. Let ej be the number of node in Cj and C' diag (C1, ..., ). The normalized version of Q is P = QC'/2 / It is easy to prove P has orthogonal columns (PP-1 I), and P.j = /2 if node i belongs to Cy; P.j = 0 if node i does not belong to Cj. The detailed coarsening algorithm will be discussed in the next section.
3 Methodology
We propose TACO, simple yet effective continual learning framework to consolidate graph knowl- edge learned from proceeding tasks by replaying previous "experiences" to the model. We observe
3

---

For task
loss
for t+1
H
Asg
MLP
May Passing
Fi
(1) m
Node Representation Proximity
Cumbine
super-made
new mode old mode
impertani aode
03
H
Gi
BU
Ri
Fideliy Presering
PPO Pill
Figure 2: An overview of TACO. At t-th time period, the model takes in the coarsened graph 9 from the last time period and the original graph G. from the current time period, and combine them into Gf; for the same time period, the selected important node set updated with the new nodes; the model is then trained on G with both the new nodes and the super-nodes from the past; finally Gf is coarsened to Gj for the next time period.
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 among tasks that result from the presence of overlapping nodes. The inter-dependencies are essential for capturing the dynamic "receptive field" (neighborhood) of nodes and improving the performance on both new and old tasks [T8]. To overcome these limitations, we design new replay method that preserves both the node attributes and graph topology from previous tasks, Our intuition is that, if store the original graphs from the old task, minimal old knowledge 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 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 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 The pscudocode of TACO is described in Algorithm T and RePro described in Algorithm in Appendix D.2
Overall framework We summarize the procedure of our framework as three steps: combine, reduce, and generate. At task we combine the new graph G. with the reduced graph 9 from the last task. Then we reduce the combined graph G to a set of clusters. At last, we generate the contributions of nodes in each cluster to form super-node in the reduced graph GT. The last step decides the new node features and the adjacency matrix of the reduced graph. We convey the details of each step below.
3.1 Step 1: Combine
We use M (e.g., hash table) to denote the mapping of each original node its assigned cluster (super-node) in reduced graph g". In the beginning, we initialize 9 as an empty undirected graph and Mo an empty hash table. At task f, the model holds copies of G M and an original graph G. for the current task. G. contains both new nodes from task and old nodes that have appeared in previous tasks. We first "combine" G. with 9 1 to form a new graph Gf by checking the hash table M,-1 and aligning the co-existing nodes in G, and G By doing so, we retrieve the inter-task edges. We train the model ff to perform node classification tasks on the combined graph Gf (A), XÇ. Y with the objective arg ming {(f 0), Yr), where f is L-layer GNN model (e.g. GCN), 0 is trainable parameters of the model, and f the loss function. new nodes and old nodes in G; 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 more detailed process in Appendix D.I
this work,

---

3.2 Step 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 reduce the size of a graph through merging "similar" nodes 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) neighhor similarity, which evaluates two nodes based on their neighborhood characteristics; 3) geometry closeness, which measures the distance between two nodes in 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 consuminn, even with approximation algorithms, making it less scalable for our applications where graphs are dynamically expanded and coarsened. Thus, aim to develop more fime-efficient algorithm that considers the aforementioned similarity measures.
To get started, we have the combined graph 9e to be coarsened. We train GNN model with T. (I. = 2 in our case) layers on gú. such that the node embedding of 9 at the first layer (before the activation function) is denoted by
H Rnd GN (At, XF,))
(I)
where d' is the size of the first hidden layer in GNN. The similarity between every connected node pair (u, v) = E E calculated based on cosine similarity as (Be) = H.,H H. where ((() the similarity score between the two end nodes of the edge e, H; is the embedding for node i, and || is the second norm of a vector. We then sort all edges of 9f such that ((e)) 2 A(e2) 2 ... 2 (((m;) )- Based on this sorted list of edges, we recursively merge two end nodes (i.e., assign the nodes to the same cluster), until the target size is reached. The class label of the merged node determined based on the majority votes of the original nodes. The new adjacency matrix and node feature matrix are discussed in Step 3. The time complexity of our coarsening process is Oddh mmf where mi is the number of edges in the current graph Gf.
Node Fidelity Preservation After multiple rounds of coarsening, the quality of graph deteriorates as its node features and labels are repeatedly processed. Furthermore, the use of a majority vote to determine the label of cluster can lead the gradual loss of minority classes and cause "vanishing minority class" problem.
Theorem 3.1. Consider n nodes with classes, such that the class distribution of all nodes is represented by p P1,P2,.... Pe. where Σi=1 1. these nodes are randomly partitioned into (. 0 < 7 < 1 and the class label for each cluster is determined via
n' clusters such that n.' [- [n. majority voting. The class distribution of all the clusters p' Phs P2,... .. P', where D3 is computed as the ratio of clusters labeled as class i and > 1 P/ = L. Let k be one of the classes, and the rest of the class are balanced p1 ... Pk-1 pk+1
Pe- It holds that:
1. Pk = 1/c and all classes are balanced p1 P2 = Pe. then Elph] = Pk-
2. When Pk 1/c, Elph] Pks, and TE pk Pk.
decreases as n' decreases. There exists a pmnnn such that
< min < 1, and when Pk < p
min
decrease as pv. decreuses.
The proof of Theorem 3.1 provided in Appendix D.3 Theorem 3.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 "replay buffer" denoted as y We adopt three strategies from [6] to select representative nodes, namely Reservoir Sampling, Ring Buffer, and Mean of Features. The replay buffer has fixed capacity and is updated new nodes are added. During the coarsening process, prevent the selected nodes in Dr from being merged by imposing a penalty on the similarity score ((e) such that
3(e) H₂ H, 1 1I E yrhh or u E Vi')
|| H.|
where é is a constant and > O. It is worth noting that we do not remove the edges of these nodes from the list of candidates. Instead, we assign high value to the penalty e. This is to prevent
5

---

scenarios where these nodes play 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 3.1. Node Fidelity Preservation with buffer size can alleviate the declination of minority class k when Pk decreases and n' decreases, and prevent class l. from vanishing when ple is small. See Appendix D.3 for further discussions.
Note that RePro does not require any additional parameters or training time. It only relies on the learned node embeddings from the graph neural network in the continual learning. We train 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 [36), by doing so, 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 similar core in terms of the preserving of graph spectral properties. See Appendix D.4 for more details.
3.3 Step 3: Generate
From the last step, we get the membership matrix Q₁ E Brfx"] where nf is the number of nodes in the combined graph, n. = L n the number of nodes in the coarsened graph and y the coarsening ratio. Q [. = denotes that node i is assigned to super-node j. Otherwise,
Q+(i,)] =
A simple way to normalize Q is assuming each node contributes equally to their corresponding super-node (e.g.
for all any node that belongs to cluster/supemode 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 node's 1 1-hop neighbors. In this step, we propose to normalize Q: to Pt utilizing these node importance information. We calculate the member contribution matrix Pt E Ro xn!_ Let i be a node belonging to cluster C₁ at timestamp f, and s; > be the importance score of node (node degree or neighbor
degree sum), then Pt,(i)) = V Exeo, 8. It is straightforward to prove that P. P. = still holds.
Once we have Pt, we get the new reduced graph 9 (Aj, XT, Y?) as:
=== = QT ARQi,
Y, = arg max V.Y
where the label for each cluster is decided by a (weighted) majority vote. Only partial nodes are labeled, and the rows of Y, for unlabelled nodes zeros and thus do not contribute to the vote.
Through training all tasks, the number of nodes in the reduced graph G" is upper-bounded by 1=2 (TMAX), where TMMA the largest number of the new nodes for each task (See Appendix D.5 D.5 for proof); when the reduction ratio y 0.5, the expression above is equivalent to 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 "MAX but we observe generally m < "MAx in practice. We claim that such a memory buffer size is reasonable for storing topology information. For instance, the default buffer size of the Cora-full dataset in SSM 55 is 4,200, which is approximately seven times the average graph size.
7

---

Empirical evaluation
We conduct experiments on time-stamped graph datasets: Kindle [14 to evaluate the performance of TACO, See Appendix E. for the details of the datasets and E.2 for hyperparameter setup.
311.
DBLP 44 and ACM 44
4.1
Comparison methods
We compare the performance of TACO with SOTA continual learning methods including EWC
(0). GEM
(291,
TWP (6).. OTG 12. ERGNN (57, SSM [55], DyGrain [T8], IncreGNNN (88)
SSRM
41
CaT
27 and DeLoMe 33
EWC and GEM were previously not designed for graphs,
so we train GNN on new tasks but ignore the graph structure when applying continual learning strategies. ERGNN-TS, 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) 6 SSRM is an additional regularizer to be applied on top of a CGL framework; we choose ERGNN-IS as the base CGL model. Besides, finetune provides the estimated lower bound without any strategies applied to address forgetting problems, and joint-train provides an empirical upper bound where the model has access all previous data during the training process.
We also compare RePro with five representative graph coarsening SOTA methods. We replace the coarsening algorithm in TO with different coarsening algorithms. Alge. JC 77, Aff.GS (28), Var. edges [30], and Var. neigh [30] are graph spectral-basee methods; FGC [21) considers both graph spectrals and node features. We follow a standard implementation [15] for the first four methods.
4.2 Evaluation metries
We use Average Performance (AP1) and Average Forgetting (AF() 66 to evaluate the performance on test sets AP and AF are defined as
T AP
1 Σ aT AF 1=1
Σ max at -arj T IE(I....TT
where T is the total number of tasks and 0;,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 Fl and balanced accuracy score (BACC), FI-AP and FI-AF indicate the AP and the AF for macro F1 and likewise for BACC-AP and BACC-AF. We calculate the macro F1 and BACC scores for multi-class classification 13
4.3 Main results
We evaluate the performance of TACO and other baselines on three datasets with three backbone GNN models, including GCN 19. GAT (46,, and GIN 44). We only report the node classification performance with GCN in Table due to the space limit. See Appendix F.T for results on GAT and GIN. We report the average values and the standard deviations over 10 runs. It shows that TOCO outperforms the best SOTA 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-Is, ER-rb, and ER-mf do not perform as well SSM and TACO, highlighting the importance 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.
4.4
Ablation studies
4.4.1 Graph coarsening methods
We evaluate the performance of RePro by replacing the graph coarsening module of TACO with five widely used coarsening algorithms while keeping other components unchanged. For each method, we report the average time in seconds consumed to coarsen the graph. We also report trade-off value which is defined as the coarsening time (in seconds) needed to increase or decrease the AP/AF by 1% compared with fine-tuning, as shown in Table 2 For instance, the trade-off for FI-AP is defined as
7

---

Table Node classification performance with GCN as the backbone on three datasets (averaged over 10 trials). Standard deviation is denoted after +.
Kindle
DBLP
ACM
Method
11-AP(%)
FI-AF
(80)
(1)
FI-AF (86)
FI-AP (8)
FI-AF
joint train
87.21
0.55
0.45
1. 0.25
86.33
1.38
0.77
0.13
75.35
1.49
1.87
0.60
linetune
+ 10.85
67.85
8.05
9.35
simple-reg
68.80 + 10.02
18:21
= 10.49
69.70
9.16
18.69
8.48
61.63
10.09
17.83
9.99
EWC
77,08
8.37
10.87
+ 8.62
79.38
+ 4,86
8.85
4.11
66.48
6.43
12.73
6.26
TWP
78,90
4.71
8.99
1. 4,93
80.05
1 3.71
8.23
1.
3.28
65.98
1 7.26
13.33
6.94
OTG
69.01
+ 10.55
18.94
68.24
+ 10.12
20.12
9.34
61.45
9.94
18.31
9.86
GEM
76.08
+ 6.70
11.01
+ 7.27
80.04
+ 3.24
7.90
2.68
67.17
- 4.24
11.69
= 3.94
ERGNN-IS
77.63
78.02
14.43
ERGNN-rb
75.87
+ 6.41
11.46
+ 6.98
75.16
7.24
12.85
6.54
63.58
+ 8.22
15.66
= 8.71
ERGNN-mf
77.28
5.91
10.15
+ 6.31
77.42
5.25
10.64
4.38
64,80
= 8.49
14.59
8.41
DyGrain
69.14
+ 10.47
18.88
67.52
+ 10.88
20.83
+ 10.16
61.40
1 9.57
18.47
9.50
IncreGNN
69.45
+: 10.34
18.48
10.66
69:40
1 9.60
18.92
1: 8.75
61.32
1 9.70
18.42
9.64
SSM
78.99
3.13
3.63
82.71
1.76
4.20
1,26
68.77
2.3
9.50
2.47
SSRM
77.37
4.0.6
9.99
4.55
77.43
5.34
10.66
= 4.47
64.39
- 7.43
14.72
= 1.48
75.12
76.24
1:314
63.72
11.86
DeLoMe
76.93
+3.83
10.16
+4.68
77.27
+2.85
8.01
16
64.54
+2.42
10.75
=2.04
TACO
82.97
2.05
4.91
+ 1,90
84.60
2.01
2.51
1,03
70.96
2.68
8.02
2.33
p-value
<0,0001
<0,0001
0.002
<0.0001
0.005
0.02
Table 2: Coarsen runtime (seconds) and trade-off results of different coarsening methods three datasets with GCN (average over 10 trials). Boldface indicates the best result of each column.
Kindle
DBLP
ACM
Method
Time (5) & TAFLAP
Time (s)
TAFLAP
Time (6) TAFLAAP 4
Algo. JC
8.9
0.74
70.8
4,08
11.8
1.19
Atf. GS
63.6
7.88
237.1
14.42
96.1
12.29
Var. neigh
6.9
0.59
0.43
10.3
1,58
Var. edges
10.1
0.77
28.0
1.63
13.8
1.24
FGC
7.7
0.63
10.8
0.64
7.0
1.05
RePro
2.3
0.17
1.1
0.07
1.4
0.13
TAFI-AP time/(FI-AP FI-AP for fine-tuning). Complete results are provided in Appendix F.2 The results demonstrate that RePro is considerably more efficient in computing time compared to all other models and achieves the best trade-off across all metrics.
4.4.2 Graph reduction rates
We examine how RePro preserves original graph information. Following the setting in [15] 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 original graphs, we train GCN models on coarsened graphs with different coarsening rates - 7. Figure (a) shows that prediction performance is relatively stable as graphs are reduced for DBLP and ACM, but Fl scores are more sensitive to reduction rate on Kindle. This may 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 the model learns similar node embeddings coarsened and original graphs. In Figure 3 (b) (d), we visualize test node embeddings on the DBLP dataset for different reduction rates using t-SNE. We observe similar patterns for and 0.5 reduction rates, and gradual changes the reduction rate increases.
4.4.3 Performance after training each task
We first investigate the performance of the model on the first task when more tasks are learned with different CGL frameworks. We also visualize the model's performance in terms of AP-F1 using the four approaches on all previous tasks after training on each task on the Kindle dataset, as shown in Figure 4 It demonstrates that the application of different CGL methods can alleviate the catastrophic

---

0.75
0.70
Kindle
DBUP
ACM
0.3 0.5
(a) GCN test
(b) - 7
(c) 0.5
(d) 1 - 0.9
Figure 3: (a) The test macro-F1 scores of the GCN model trained on the coarsened graphs with different reduction rates three datasets. (b)-(d) t-SNE visualization of node embeddings of the DBLP test graph with reduction rate of O, 0.5, and 0.9 the training graph respectively.
forgetting problem on the Kindle dataset as we point out in the introduction part to varying degrees. Also, observe that the performance of experience replay-based methods (SSM and TACO) are more stable through learning more tasks, but the regularization- based method, TWP, experiences more fluctuations. We deduce that this is caused by the fact that regularization-bass better prevent the model from drastically forgetting previous tasks even when the current task has more distinct distributions.
methods can
4.5 Efficiency analysis
To ensure fair comparisons, for experience replay-based methods, adjust the memory buffer size so each model stores comparable average numbers of replay nodes. We report the average memory usage of each model on each task in Table[[OJin Appendix G.3) Since TACO needs extra space to save topology information, its memory usage slightly larger compared to methods that don't It preserve graph structures. We provide memory usages of the representative methods across tasks Table S
4.6 Additional studies
For those readers who are interested, we also evaluate the short-term forgetting G.. and the performance the CGL frameworks when each task is assigned with shorter time intervals G.2 We study the effectiveness of the Node Fidelity Preservation (G.4). and the effects of different important node selection strategies G.5). We also evaluate TA CACO on traditional daass-nccremental learning
(G.6) to prove its generalizability. We present those results in Appendix G
finetune
TWP
SSM
ours
62.8
86.8
Training task
63.6
36.4
T took
78.4
86.
Training taol
82.8 36.4
Training
56.0
44.6
86.1
69.4
60.6
86.0
78.7
72.4
85.3
76.0
68.4
86.2
62.1
68.7
52.7
87.0
77.0
76.6
67.2
87.4
78.3
76.6
75.2
86.1
80.8
76.9
76.0
87.7
64.0
69.0
64.8 58.9
88.8
78.8
77.4
75.3
74.9
88.1
79.8
75.8
78.2
74.5
86.6
83.5
79.6
80.5
83.8
87.4
1
3
4
1
2
5
3
4
Test task
Test task
Test task
Test task
Figure 4: Fl score on the test set (x-axis) after training on each task (y-axis) on Kindle dataset.
Related Work
Regularization, Expansion, and Rehearsal are common approaches overcome the catastrophic forgetting problem 43 in continual learning. Regularization methods 20 4 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 43 B5] where the previously regularized parameters may become obsolete and unable to adapt to new tasks.
52
10 penalize
16 23 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-basee methods consolidate old knowledge by replaying
Expansion- methods 40 51

---

the model with past experiences. A common way is using small episodic memory of previous data or generated samples from generative model when trained on new tasks. While generative methods [ 2
may use less space, they also struggle with catastrophic forgetring problems
and over-complicated designs [8 Experience replay-based methods (39
43 29], on the other
hand, have 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, [26] address catastrophic forgetting by penalizing the parameters
that are crucial to both task-related objectives and oppoloyy-relttee ones. [41] mitigate the impact of
the structure shift by minimizing the imput distribution shift of nodes. Rehearsal- -base methods [18]
57 48 keep memory buffer to store old samples, which treat replayed samples as independent data
points and fail to preserve their structural information. [5.5] preserve the topology information by storing a sparsified L--hpp neighborhood of replay nodes. However, storing topology information of nodes through this method is not very efficient and the information of uncovered nodes completely
lost; also it fails capture inter-task correlations in our setup. Besides, [12] 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. (27) uses a condensed graph the memory buffer and employs "Training in Memory" scheme that directly learns the memory buffer to alleviate the data imbalance problem. However, the condensed graph contains only sampled nodes with self-loops, resulting in the loss of valuable topology information. [33] stores the learned representations of the sampled nodes as a memory store, which can preserve graph structure information. However, it still cannot handle inter-task edges, and the stored representations are inadequate for dealing with the dynamic receptive field of old nodes when new nodes form connections with them. Some CGL work [47 50) 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 pivotal role.
To better highlight the advantages of our proposed method, we provide a comparison between our method and these experience-ber based methods in Table 3 Our method, TACO, is the only one that can preserve graph topology, handle inter-task edges, and consider the growing receptive field of old nodes.
Table 3: Comparision between experience replay- based CGL methods.
ERGNN
DyGrain
IncreGNN
SSRM
SSM
SEM
C:T
DeLoMe
PGDNN
TACO
S7
AS
41
SS
56
33
53
Replay buffer
Node feat. Node feat.
Node feat.
Noda fear. Sparsified Sparsitied Condensed Node
Decoupled node repre. graph
Coarsend
graph
graph
gruph
repre.
Graph topology
X
X
X
X
Inter-task edges
X
X
X
X
X
X
X
Dynamic reception field
X
X
X
X
X
Conclusion
In this paper, we present a novel CGL framework, TACO, which stores useful information from previous tasks with dynamically reduced graph consolidate learned knowledge. Additionally, propose an efficient embedding proximity-base graph coarsening method, RePro, that can preserve important graph properties. We present Node Fidelity Preservation strategy and theoretically prove its capability in preventing the vanishing minority class problem. We demonstrate the effectiveness of TACO and RePro real-world datasets with realistic streaming graph setup.
Acknowledgements
We thank the anonymous reviewers for their helpful comments. This work supported in part by the US National Science Foundation under grants 2047843, 2437621, and 22 12370.
10

---

References
[1] Alessandro Achille, Tom Eccles, Loie Matthey, Christopher P. Burgess, Nick Watters, Alexander Lerchner, and Irina Higgins. Life-long disentangled representation learning with cross-domain latent homologies. CoRR, abs/ 0ass/1808.00 558806608, 2018.
[2] Lucas Caccia, Eugene Belilovsky, Massimo Caccia, and Joelle Pincau. Online learned continual compression with stacked quantization module. CoRR, abs/ 190./999,,,,19, 2019.
[3] Antonio Carta, Andrea Cossu, Federico Errica, and Davide Bacciu. Catastrophic forget- ting in deep graph networks: an introductory benchmark for graph classification. CoRR, abs/2103.117555 17500, 2021.
[4] Arslan Chaudhry, Puneet Kumar Dokania, Thalaiyasingam Ajanthan, and Philip H. S. Torr. Riemannian walk for incremental learning: Understanding forgetting and intransigence. CoRR, abs/1801.1011 2018.
[5] Arslan Chaudhry, Marc' Aurelio Ranzato, Marcus Rohrbach, and Mohamed Elhoseiny, Efficient lifelong learning with A-GEM. CoRR, abs/1 (12.0020, 2018.
[6] Arslan Chaudhry, Marcus Rohrbach, Mohamed Elhoseiny, Thalaiyasingam Ajanthan, Puneet Ku- mar Dokania, Philip H. Torr, and Mare' Aurelio Ranzato. Continual learning with tiny episodic memories. CoRR, abs/1 902. 10486, 2019.
[7] Jie Chen and Ily Safro. Algebraic distance on graphs. SIAM Journal on Scientific Computing, (16):3468-3490) 2011.
[8] Kamil Deja, Pawet Wawrzyáski, Daniel Marezak, Wojeiech Masarczyk, and Tomasz Trz- ciñsski. Binplay: A binary latent autoencoder for generative replay continual learning. In 2021 International Joint Conference on Neural Networks (IJCNN, pages 1-8, 2021.
[9] Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang, and Zhuo Feng. Graph- zoom: A multi-level spectral approach for accurate and scalable graph embedding. CoRR, abs/1910.02370, 2019.
[10] Sayna Ebrahimi, Mohamed Elhoseiny, Trevor Darrell, and Marcus Rohrbach. Uncertainty- guided continual lcarning with bayesian neural networks. CoRR, htts/1906.02255. 2019.
[11] Matthew Fahrbach, Gramoz Goranci, Richard Peng, Sushant Sachdeva, and Chi Wang. Faster graph embeddings via coarsening. CoRR, his/2007.022177 2020.
[12] Kaituo Feng, Changsheng Li, Xiaolu Zhang, and Jun Zhou. Towards open temporal graph neural networks, 2023.
[13] Margherita Grandini, Enrico Bagli, and Giorgio Visani. Metrics for multi-class classification: an overview, 2020.
[14] Ruining He and Julian J. McAuley. Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. CoRR, abs/1602.01188, 2016.
[15] Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neural networks via graph coarsening. CoRR, abs/2106.05155 2021.
[16] Ghassen Jerfel, Erin Grant, Thomas Griffiths, and Katherine A. Heller. Online gradient- based mixtures for transfer modulation in meta-learning. CoRR, abs/1 8 22. 220600, 2018.
[17] Yu Jin, Andreas Loukas, and Joseph JaJa. Graph coarsening with preserved spectral properties. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 4452 4462. PMLR, 26-28 Aug 2020.
[18) Seoyoon Kim, Seongjun Yun, and Jaewoo Kang. Dygrain: An incremental learning framework for dynamic graphs. In Lud De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 3157-3163. International Joint Conferences on Artificial Intelligence Organization, 7 2022. Main Track.

---

[19] Thomas N. Kipf and Max Welling, Semi Semi--supervieed classification with graph convolutional networks. CoRR, abs/1609.02990 02907, 2016.
[20] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Wtrabsk-BBarwinskee Demis Hassabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell. Overcoming catas- trophic forgetting in neural networks. Proceedings of the National Academy of Sciences, (14(13):3521-3222 mar 2017.
[21] Manoj Kumar, Anurag Sharma, and Sandeep Kumar. A unified framework for optimization- based graph coarsening. 2022.
[22] Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors. Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 3734- 3743. PMLR, 09-15 Jun 2019.
[23] Soochan Lee, Junsoo Ha. Dongsu Zhang. and Gunhee Kim. A neural dirichlet process mixture model for task-free continual learning. CoRR, abs/2001 .00689, 2020.
[24] Jiongqian Liang, Saket Gurukar, and Srinivasan Parthasarathy. MILE: A multi-level framework for scalable graph embedding. CoRR, abs/1802.00612, 2018.
[25] Chuang Liu, Yibing Zhan, Jia Wu, Chang Li, Bo Du, Wenbin Hu, Tongliang Liu, and Dacheng Tao. Graph pooling for graph neural networks: Progress, challenges, and opportunities, 2023.
[26] Huihui Liu, Yiding Yang. and Xinchao Wang. Overcoming catastrophic forgetting in graph neural networks. CoRR, abs/2012.06003 2020.
[27] Yilun Liu, Ruihong Qiu, and Zi Huang. Cat: Balanced continual graph learning with graph condensation, 2023.
(28) Oren E. Livne and Achi Brandt. Lean algebraic multigrid (lamg): Fast graph laplacian linear solver. SIAM Journal on Scientific Computing, 34(4):B499-B522, 2012.
[29] David Lopez-Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continuum learning, CoRR, abs/1706.0886 088400 2017.
[30] Andreas Loukas. Graph reduction with spectral and cut guarantees. CoRR, abs/180 808. 10650, 2018.
[31] Julian J. McAuley, Christopher Targett, Qinfeng Shi, and Anton den Hengel. Image- based recommendations on styles and substitutes. CoRR, abs/1 550.044767 2015.
[32] Fei Mi, Lingjing Kong, Tao Lin, Kaicheng Yu, and Boi Faltings. Generalized class incremen- tal learning. In 2020 IEEE/CVE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pages 970-974, 2020.
[33] Chaoxi Niu, Guansong Pang, and Ling Chen. Graph continual learning with debiased lossless memory replay, 2024.
[34] Oleksiy Ostapenko, Mihai Marian Puscas, Tassilo Klein, Patrick Jähnichen, and Moin Nabi. Learning to remember: A synaptic plasticity driven framework for continual learning. CoRR, abs/1904.031377 2019.
[35] Pingbo Pan, Siddharth Swaroop, Alexander Immer, Runa Eschenhagen, Richard Turner, and Mohammad Emtiyaz E Khan. Continual deep learning by functional regularisation of memorable past. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 4453 4464. Curran Associates, Inc.. 2020.
[36] Ying Pan, De-Hua Li, Jian-Guo Liu, and Jing-Zhang Liang. Detecting community structure in complex networks via node similarity. Physica A: Statistical Mechanics and its Applications, 389(14):2449-857) 2010.
12

---

[37] Yunsheng Pang, Yunxiang Zhao, and Dongsheng Li. Graph pooling via coarsened graph infomax. CoRR, abs/2105.01275, 2021.
[38] German Ignacio Parisi, Ronald Kemker, Jose L. Part, Christopher Kanan, and Stefan Wermter. Continual lifelong learning with neural networks: A review. CoRR, abs/1 802.07769,, 2018.
[39] David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy Lillicrap, and Gregory Wayne. Experi- ence replay for continual learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- -uch E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[40] Andrei A. Rusu, Neil C. Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. CoRR, abs/1606.0461 2016.
[41] Junwei Su and Chuan Wu. Towards robust inductive graph incremental learning via experience replay, 2023.
[42] Lichao Sun, Yingtong Dou, Carl Yang, Kai Zhang, Wang. Philip S. Yu, Lifang He, and Bo Li. Adversarial attack and defense on graph data: A survey. IEEF Transactions on Knowledge and Data Engineering, page 1-20, 2022.
[43] Binh Tang and David S. Matteson. Graph-based continual learning, 2020.
[44] Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Areeminee: Extraction and mining of academic social networks. KDD '08, pages 990-998, 2008.
[45] Gido M. van de Ven and Andreas S. Tolias. Three scenarios for continual learning. CoRR, abs/1904.07734, 2019.
[46] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks, 2017.
[47] Yuening Wang, Yingxue Zhang, and Mark Coates. Graph structure aware contrastive knowledge distillation for incremental learning recommender systems. In Proceedings of the 30th ACM International Conference on Information and Knowledge Management, CIKM '21, page 3518-3522, -322,, New York, NY, USA, 2021. Association for Computing Machinery.
[48] Di Wei, Gu, Yumeng Song, Zhen Song, Fangfang Li, and Ge Yu. Incregnn: Incremental graph neural network learning by considering node and parameter importance. In Databuse Systems for Advanced Applications: 27th International Conference, DASFAA 2022, Virtual Event, April 11-14, 2022, Proceedings, Part I, page 739-746, Berlin, Heidelberg, 2022. Springer-Verlee
[49] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks?, 2019.
[50] Yishi Xu, Yingxue Zhang, Wei Guo, Huifeng Guo, Ruiming Tang, and Mark Coates, Graphsail: Graph structure aware incremental learning for recommender systems. CoRR, 0tbs/2008.135111 2020.
[51] Jachong Yoon, Eunho Yang, Jeongtae Lee, and Sung Ju Hwang. Lifelong learning with dynamically expandable networks. CoRR, abs/1708.01547, 2017.
[52] Friedemann Zenke, Ben Poole, and Surya Ganguli. Improved multitask learning through synaptic intelligence. CoRR, Abs//1703.04200, 2017.
[53] Xikun Zhang, Dongjin Song, Yixin Chen, and Dacheng Tao. Topology-aware embedding memory for continual learning expanding networks. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, volume 33 of KDD '24 page 4326. ACM, August 2024.
[54] Xikun Zhang, Dongjin Song, and Dacheng Tao. CGLB: Benchmark tasks for continual graph learning. Tiih Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
13

---

[55] Xikun Zhang, Dongjin Song, and Dacheng Tao. Sparsified subgraph memory for continual graph representation learning. 2022 IEEE International Conference on Data Mining (ICDM), pages 1335-1340, 2022.
[56] Xikun Zhang, Dongjin Song, and Dacheng Tao. Ricci curvature-based graph sparsification for continual graph representation learning. IEEE Transactions on Neural Networks and Learning Systems, pages 1-13, 2023.
[57] Fan Zhou, Chengtai Cao, Ting Zhong, Kunpeng Zhang, Goce Trajcevski, and Ji Geng. Over- coming catastrophic forgetting in graph neural networks with experience replay. CoRR, abs/2003.09908, 2020.
[58] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery, KDD '18. ACM, July 2018.
14

---

Appendix
A Limitations
This work only considers situations where nodes and edges added to streaming graphs with a single relation type. In the future, we plan to investigate CGL methods when nodes and edges can be deleted modified. Moreover, will generalize method to complex graphs such as multi-relation graphs and broader graph tasks such as link prediction for recommendation systems.
B Broader impacts
By alleviating the forgetting problem in graph continual learning, the proposed TACO model retains old knowledge while integrating new information. This crucial for maintaining accurate and reliable models in critical domains with constantly evolving data, such as healthcare, biomedical informatics, and knowledge graphs
C Related work on Graph Coarsening
Scalability is major concern in graph learning. Extensive studies aim to reduce the number of
nodes in graph, such that the coarsened graph approximates the original graph [7
30
7
28
In recent years, graph coarsening techniques are also applied for scalable graph representation
learning [4 [5] and graph pooling (37 25 Most graph coarsening methods [7 30 7 28
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 graph needs to be repetitively reduced. Also, the aforementioned methods rely solely graph structures but ignore node features. 21 propose to preserve both spectral properties and node features. However, it models the two objectives separate optimization terms, thus the efficiency problem from the spectral-bare based methods remains.
D
Supplemental Methodology
D.1 Overall framework
In the proposed framework, during the training process, we use reduced graph G" as approximate representation previous graphs, and function MM() (e.g.. hash table) map each original node to its assigned cluster (super-node) in G" (c.g., if an original node is assigned to cluster j. then M(1) = j). Both 9 and MM(+) are updated after the 1-th task.
To get started we initialize 9 as an empty undirected graph and Mo as an empty hash table. At task T,, the model holds copies of g; M,- and an original graph G, for the current task.
We combine G. with - to form a new graph 9i according to the following procedure:
1. Initialize the combined graph G = (A7, Xf, Yf)) as G such that Ab = -A-11- Xi = X and
Y, =Y_
Case I: new source node and new target node. For each edge (s, &,, if ((s) = =(() = t, we add and to Gū and we add undirected edge (s,0) to G
Case 2: new source node and old target node. T(s = t, but r(o) < t,, and E M we add to Gū. and we add an undirected edge (s, (M-1 G;:
Case 3: deleted targel node. If (()) < and o ş Mr-1, we ignore the edge.
5. When new node v is added to G it is also added to M and is assigned to new cluster.
It is worth noting that we use directed edges to better explain the above procedure. In our implemen- tation, the combined graph is undirected since the directness of the edges the combined graph not critical in learning node embeddings in graph like citation network.
15

---

D.2 Pseudocode
The pseudocode of the proposed TACO is described in Algorithm [ and the graph coarsening process RePro is described in Algorithm 2
Algorithm The Proposed Method TACO
1: Input: A sequence of graphs G Gb (Ge is only accessible at task t)
2: Output: A trained GNN node classifier f with parameter
3: Mo, 1/ +- Ø; 0.0
4: for task
do
5: (G:: M <- combine(G, Mt-1
6: for epoch=0 to num num_epoch
7:
Train f on Gf and update 0
8:
end for
9:
Vr + SSamplingStrateey(>rt
10:
Compute node embedding H, based on Eq. I
11: Pt, Qt, P(.)
SarrehCaranniggggorrtmmtf 12: Compute G. based on Eq. 3
H,, V
Mr Me(v)= = P(M (v)) for Mi-1
14:
end for
15:
16:
function COMBINE(C, M
Of -
18: for each edge (s, 0) E & do then Add and to gj and M Add an undirected edge from on 9;
if T(s) = T())
20:
22:
else
T(s) and T(s) < and MM then Add to G; and M,-1
24:
Add an undirected edge from (o) on 9 end if end if
26:
27:
end for
28:
Return 9j, M
29:
end function
D.3 Node Fidelity Preservation
Theorem 4.1. Consider nodes with classes, such that the class distribution of all nodes is where Ei.1 Pi =1=1. If these nodes are randomly partitioned into n' clusters such that n' Ly n., 0 < y <1 and the class label for each cluster is determined via majority voting. The class distribution of all the clusters is p v'1, P2y,.., ".,,. where Pt is computed as the ratio of clusters labeled as class and Σi= p/ = Let one of the classes, and the rest of the class are balanced
represented by p P1,P2,
Ph-1 Ph+1
Pe. It holds that:
1. If pk 1/c and all classes are balanced p1 P2
Pe: then Elp')] Pk.
When ps 1/c. Elpp]] < Pk- and E decreases as n' decreases. There exists a mmnn such that
0 < min < 1, and when Pk mile
decrease ps decreases.
P
Proof. We prove the theorem by deriving the value of E[ppA1 Since Elp(]] is invariant to the order of the classes, for convenience, we consider = without losing generability. The probability of the first class after the partitioning is:
1 Σ n
Elp =
B(nalq(,,p)
(5)
16

---

Algorithm 2 The Proposed Graph Coarsening Algorithm RePro
Input: The original graph G, node embedding matrix H, node sets Vob, and the reduction rate ?
2: Output: partition matrix Q, normalized partition matrix P, and the mapping function P(+)
Initialize the mapping function P(-) such that P(v) for
4: n" - [V]
5: n target < Lr- [
6: Sort edges
in the descending order based on their similarity scores calculated according
to Eq. 2
7: for each edge == (u, v) do
8:
if P(u) # P(c) then if u and v are different clusters
9:
10:
Merge the clusters of and such that P(u) -((c) 12" = =n"=
11:
12:
end if
13: if n" < target then
14:
Break
15: end
16:
end for
17:
Construct Q with P(-); compute P based on Pt,(i) = V Excc,
st
18:
Return P.P.)
where E|na] is the expectation of number of clusters containing a nodes, and g(a, p) is the probability that class is the majority class in cluster with size
Property D.I. The expectation of the number of clusters containing a node is
a-1 Proof. Define I to be the indicator random variable for the jth cluster, such that:
n (-="'+1)
+1
a-n' (a-1)
B[na] n' x
1 - f1
if the jth cluster contains exactly a samples, otherwise.
We first compute the expected value of I, for a single cluster. Let's calculate the probability that
1 out of the n'' samples allocated to the jth cluster:
(a) There are (a=n') ways to choose samples from the n' remaining samples.
(b) The probability that each of these samples is placed in the jth cluster is (+))-1
(c) The remaining n - a + samples from our original pool of n n' should not allocated the 7th cluster. The probability that all them avoid this cluster (1 ) "==="'((a-1)
Thus, the probability that the 5th cluster contains exactly x samples is:
T1 n
1 a-1 n
n-n (a-1)
B
(6)
a
The expected number of clusters out of all n clusters that contain exactly samples is:
n' [[
E na
j=1
17

---

Given that each 1 is identically distributed, we can simplify the sum
E[mo] = n'' x E[T,]-
(8)
Substituting the expression derived for [[[,]] from step 2, we obtain:
n1 n¹"
1
a-1
1
n-n' (a-1)
B|nal =n'x
(9)
n
casy to show that when p1 = P2 = = Pe. it holds that a(a, ! since classes are equivalent and have equal chances to be the majority class. Thus:
1 n
B Eli
E[nolg(a,p))
1
E [[no]
- n¹'
a-1
n- n-n'
(10)
n'
1
n1
n
n
1
n
To compute q(a, p), need consider the situations in which class is the exclusive majority class and the cases where class I ties with one or more other classes for having the most samples. In the second case, we roll a die select the majority class from all the classes that have most samples.
To start, we consider the situation when class has the most nodes and no other classes tic with We enumerate all possible combinations of class assignments and calculate the probability of each.
go(a, p)
Σ
in
f(i,
(11)
where i1, dg.. and
f(i,,p))
a
i1... - is
Pk it
(1
px) pa-
(12)
it
and
P1
i
Pk
P1
otherwise
(13)
We then consider the situation when class ties with another class. We first select another class that ties in with class and enumerate the possibility of other classes. We multiply the whole term by as there is an equal chance to select either class as the majority class.
()
1 Σ
ΣΣ
Σ
I is a)f(p.p))))
(14)
h=
11=0
t==0
A=
18

---

We extend the above equation to general case where class ties with k classes (1 v A S c 1). Here we need to select k classes that tie with class 1. Class now shares K4I chance be selected the majority class with the selected & classes.
c-
c-k+1c 1ettc-kkt k+2
9& (a. p)
Σ
Σ
Σ
21 J2
JN 1--1
(15)
1=1
1-11
ΣΣ
Σ
a)S(i.a.p).
is
1=1
83 =11
f/2 =1
1==0
k=
Finally, we combine all the cases, and the probability that class I is the majority class is:
((a. p) Σ (< p).
(16)
k=0
The expectation of El thus:
1
E
E
[mn]a(aa p).
(17)
P1
P1 n
To study the behavior of B
when pl changes, we derive the following derivative:
pi
dE
B[na]g(a, p)
dp1
dpi
(18)
n2'
d (a.
Ra
P1
n
dp1
where
d2(a.p)
1 dktla.p)
dp1
dpi
b- k+ 1 c- k+2
c-
i
11
d
S(a..p)
= マ Σ
Σ
Σ
4 =
a)
dp
1=
1==
je=ja-1
i==1
1==0
f =11
Su =i1
t==0
(19)
19

---

To find
P1
first separate the terms that are independent of pi:
dp
f(1.a. p)
i1...
is
PK
(1
PP&)
P1
i
k=1
a
11...
ik
II Pie (1 - pk. j--i
P1
dk
k=1
i1...
2b
p1
- (1 -pi))
Pl
Ei
1 P1 j i4...
c 1
(20)
Pi
(1 p1)
وー (1 pi
Ei (p1 + +c- ()-2)Et-a--b..)
a i 2
u X
x (1 - (P))
0 i2... in
(p1 + 2)k=
where u is independent of p1
II
11... is
u
(21)
ik
c
We observe that f(,a.p) demonstrates different behaviors for and and discuss the two cases separately.
(1) When a 1. it holds that i1 = 1, 0 = 0, á = 0, and e = O:
f(i, a. p) u pi - (p2 -2)) u.
(22)
P1
(l..p) dp
In such case,
is independent with and remain constant when P1 changes.
(2) When a > 1. it holds that i S 1, 0.0 0, δ
0, 2 2 0, and 0 + > 0:
(i.a.p)
u pd 0- (1-)) (p+ c- 22
(23)
dpi
where
== 0(1 p) - + c 2) + 1p - p) - 6p(p + 2)
2)
(24)
= (-0 o ")pp + (0 + + (Ø -0 - 2))p + +((c -2)) 2).
d p(...pp)
When 0 < P1- < 1 and u > 0,
if and only if v = 0, and the corresponding value of p
dp1
is:
(0 0- (c- + n) V
p
(25)
2 2--0 - 0 - v)
- (0 0- (c ()c-2)+3 + n) + VA
p
(26)
2 2--0 V)
20

---

where
A (0- - 0.000.00 (c (c- 2) 3 (c- 2))² - 4 (--0 0- o- 2) (0 (c 2)).
(27)
is easy to show that A > 0, and since (-0 Φ v) < 0, v concave, when pt < < pl.
Also, it is observed that when 0,
0(c 2) 0:
(28)
when P1 1,
1 - 1) < O.
(29)
Thus must be held that 0 < < and pl $ 0, and for any (i, > 1), there exist a 0 < pı
1)0 < such that when pı < pi,,,, 1),
P1
0. Let
dp
pl
min
min
p (1,
(30)
F (2....' J.
d
where I is all possible then holds that p
1, and when P1 < ph
21
>
0.
dp1
Next, we show that E Li decreases n' decreases when P1 < 1/c. We first rewrite E as
1
E
E E|malq(a.p)
P1
P1
(31)
n'
n-n'-(a-)
n
n'
1
((a.p)
P1
n
Tt'
First, we show that q(a, p) is smaller for larger when pı < 1/c. The intuition is that when new node added to cluster originally with 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, (a=1) (1) (1- +) n "a"""""'"- (a-- becomes more left-
skewed, that it gives smaller value for large a. The intuition is that, as the value of n' increases, the average cluster size expected to decrease. As result, large becomes farther from the average cluster size, and the probability of a cluster having exactly nodes decreases, leading to a decrease in the ratio of clusters with size
With the above observations, it can be concluded that when 1/c,, the value of E(Pi| p1
decreases
as n' decreases.
Node Fidelity Preservation with buffer size can alleviate the declination of minority class when pv: decreases and n' decreases, and prevent class le from vanishing at small when Pk is small.
Observation 4.1.
The mechanism of Node Fidelity Preservation is to "hold" b clusters such that each cluster only has 1 node. We already show that when 1, g(c.p) is independent of qi and Esyí] = Pr. By doing so, we make sure that among the nodes, class does not decline as pı or nt' decline.
2i
We demonstrate the effect of Node Fidelity Preservation with examples. We assign n = 1000, 3,3, and |n' we plot change of [E( and E[p[] at different n' and p1 separately in Figure 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 E approaches zero when n' is small, resulting vanishing minority class. The application of Node Fidelity Preservation prevents the ratio from approaching zero and makes sure class won't i disappear when pı is small.
21

---

0.05
0.3n
0.30
0.50
Reb 161
0.0
(a)
18
Vs. P1.
(b) Blp1
VS. P1.
P1
0.00
0.1n
0.3h
0.5
0.7
0.2
0.6
0.5
6.8
10
0.0
VS. Pl.
(d) Blyl VS. Pl.
[ against at different reduction rate 7 for c = 2 and c = 3. The dashed lines represent trends with Node Fidelity Preservation (NFP), and the solid lines represent trends without NFP.
Figure 5: Elp]] and
D.4 Node Representation Proximity
Spectral-based methods aim to preserve the spectral properties of graph. Specifically, the Laplacian matrices of the original graph and the reduced graph are compared with each other 30 The combinatorial Laplacian of graph G. I. E R defined as I. D A, where A E R the adjacency matrix of G. and D E g2x= is its diagonal degree matrix. The combinatorial Laplacian of the reduced graph, L' E Ra 'nn' is calculated L' P LP* where p+ is the pseudo inverse of the normalized coarsening matrix P Roxn', and PF is the transposed pseudo inverse of P. Since and T' have different sizes, they can not be directly compared. Instead, the following induced semi-norms defined:
||>|| = Vx Lx, || V'''L'''
(32)
where z E RR, and x' the projection L to L' can be defined as how close ||æ|| is to | L and L' are considered equivalent if it holds ||æ'||z/ = ||>|| for any x E R". We next show that a partitioning made by merging nodes sharing the same neighborhood structure results in equivalent Laplacian of the reduced graph as the original graph.
on n' n'-space such that x' Px. The closeness between
Theorem D.I. Let i and] be two nodes of 9, A E Bexn be the adjacency matrix of G and Ā A+I, D be the diagonal matrix of A and Í = D + T, P Raxn-1 be the normalized coarsening matrix by merging and j to one node, and I,' be the combinatorial Laplacian of G and the reduced graph. holds that A, = A, D. = D + ||>||| || for any IR" and x' = Pa., where A; the i-th row for matrix A.
Proof. Given that A, = Å, and D, = Dj, denote these common rows as Ai and D.j, respectively.
The norm | is defined as:
||ا|| = x" Lx.
where L D A the combinatorial Laplacian of g. Similarly, for the coarsened graph, the norm ||a:']].- is defined as:
| ||. = (Px) L'
where L' is the combinatorial Laplacian of the coarsened graph.
22

---

We need to show that ||ا|| = || Ilz..
First, consider the left-hand side norm:
|| = x² La x x² A)x.
Given the structure of Á and D, we have:
|
DDAtR Σ
Auzzz
When merging nodes i and j. the coarsening matrix P combines these two nodes into one. Thus, x'
Pr.
The matrix P such that it preserves the sum entries corresponding to the merged nodes, maintaining the structure of the Laplacian. Therefore, have:
P-P=II (except for the merged nodes).
The reduced Laplacian L' after merging i and j incorporates the sum of the rows and columns corresponding i and j in Á and D. Since A, A, and D, Dj. the rows and columns corresponding to and j are identical, thus preserving the overall structure and norm.
Therefore, have: | (Px)' =x Lx ||=||
D.5 Proof of the size of the reduced graph
Proof. The number of nodes of the reduced graph at task t is:
(1 (1..((11 7)m1 + 1z2)... + n4)
(1 (.. - 7)Mx + -1MAA)... + mMMx))
((1 - 7) + (1 - 7)² +... + (1 (11-))))
7 TMAX
D.6 Discussion utilizing soft labels as alternative to majority voting
Another potential solution to address the "vanishing class" problem caused by the majority voting is to soft labels to represent the cluster label instead. However, such approach may come with several brawbcck.. First, using hard labels is memory-efficient, and requires only a single digit to represent sample's ss label. In contrast, soft labels use vector for storage, with 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 large number of classes, the increased memory demand soft labels becomes significant and cannot be overlooked. Second, although model can learn to predict 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 performing a regression task. To predict single nodes with deterministic labels, it is considered suboptimal approach to model it as regression task due to the unaligned optimization objectives and loss functions. Also, regression believed 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.
23

---

Table Statistics of datasets. "Interval" indicates the length of the time interval for each task. " Item" indicates the total number of items/papers in each dataset.
Dataset
Time
Interval #Task #Class #ltems
Kindle
2012-2016
1 year
5
6
38,450
DBLP 1995-2014
years
10
4
54,265
ACM 1995-2014
years
10
77.130
E
Supplemental experiment setups
E.1
Details of the datasets
The Kindle dataset contains items from the Amazon Kindle store; each node representing an item associated with a timestamp indicating its release date, and each edge indicates a "frequently co-purchased" relation between items. The DBLP and ACM datasets are citation datasets where each node represents a paper associated with its publishing date, and a node's connection to other nodes indicates citation relation. For the Kindle dataset, we select items from six categories: Religion & Spirituality, Children s eBooks, Health, Fimess & Dieting, SciFi & Fantasy, Business & Money, and Romance. For the DBLP dataset, select papers published in 34 venues and divide them into four classes: Database, Data Mining, AI, and Computer Vision. For the ACM dataset, we select papers published in 66 venues and divide them into four classes: Information Systems, Signal Processing, Applied Mathematics, and AI. For each of the datasets, we select nodes from a specified time period. We build 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 paper published in the future. Then 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 randomly select one
sets of class labels, each task for the Kindle dataset, 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
classes and
E.2 Hyper-parameter setting
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'|a E [-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 a similar scale to that of CO. For TACO, by default the reduction ratio is 0.5; memory buffer size for Node Fidelity Preservation is 200; node degree 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 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 NVIDIA GeForce RTX 3090 GPU.
F
Additional results
F.
Main results
We present more results of the performance of TACO and other baselines on three datasets and two additional backbone GNN models, 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.
24

---

Table 5: Performance comparison of node classification in terms of F1 and BACC with GAT three datasets (average over 10 trials). Standard deviation is denoted after +.
Dataset Method
F1-AP (%)
F1-AF (%) 4 BACC-AP (%)
BACC-AF (%)
joint train
88.54:0.70
0.35+1..27
82.71+1.02
0.62=00.46
finetune
68.68=11.55
20.05=11.559
66.8914.90
16.91
simple-reg
66.20=10.89
19.26+11.18
64.61
15.24-14.48
EWC
78.95+:5.62
9.92-+5.79
73.4942.76
10.30+33.33
TWP
78.17:6667
10.85:1.771
73.2343.06
10.78+13.58
OTG
70.09:19.66
18.78110.02
67.50114.24
16.53:14.65
Kindle
GEM
76,46117.14
11.86:7.61
72.5212.56
10.97
ERGNN-rS
78.64+4.33
9.56+4,57
72.19+2.95
10.70
ERGNN-rb
75.60=7.14
12.66+7.34
71.86+3.16
11.55+3.32
ERGNN-mi
78.1445.22
10.35+5.55
72.94+3.05
10.90=3.89
DyGrain
10.05
18.28
68.16.14.05
15.7714.889
IncreGNN
10.66
18.1
68.06114.50
15.92.15.006
SSM
81.84112.10
6.58-12.59
74.64.1..10
8.81-12.62
SSRM
78.09:4.54
10.20:5.15
71.99:2.46
11.17=3.39
TACO
83.66=1.93
4.69:11822
76.58:3.007
6.34-22.13
joint train
83.43++1.81
1.08+
76.97:11.94
1.79:+0.64
finetune
65.75=10.67
21.68
64.21+4.21
18.76+33228
simple-reg
68.85-19.68
18.4918.55
66.2114.00
16.71
EWC
76.33+:5.71
11.12+5.02
71.05+3.83
12.16+3.44
TWP
76.6444..47
10.61+3.77
70.95+3.22
12.03++2.98
OTG
67.50=10.70
20.06+9990
65.65+4.40
17.57+3..63
DBLP
GEM
73.64:16.07
12.76.14.77
67.53.14.47
14.42.13.24
ERGNN-IS
75.36:15.62
11.8714.62
70.0713.88
12.95
ERGNN-rb
71.65.17.32
15.20.1.34
67.1611..86
15.37
ERGNN- mf
74.62=6.11
12.55+5.29
68.97
13,90#3.61
DyGrain
65.83=10.05
21.62+8.96
63.80+4.18
19.10=2.71
IncreGNN
66.23=11.16
21.23+10.52
64.6244.110
18.55#3.41
SSM
81.47-42.48
1.46+
74.62+2.41
6.48
SSRM
74.31+6.00
12.63+44.68
69.15+4.18
13.57+3.41
TACO
81.63++1.06
2.29+-0.60
76.08+11667
1.59
joint train
74.89+11.53
1.91+0.85
65.81++1.40
2.32+1133
finetune
61.89
17.79110.44
58.0542.118
14.24
simple-reg
59.22.+9.95
17.79+9.81
55.88+2.90
14.23+1.557
EWC
66.75.1.00
12.20.6.93
61.49.1.84
10.4411.75
TWP
67.42.17.54
11.66.1.33
61.57.1..22
10.29
OTG
62.24
16.99111.02
58.5512.377
13.70
ACM
GEM
67.01=4.61 11.1644.47
59.5342.44
10.68+2.06
ERGNN-IS -T
64.89+7.93 13.9047.88
59.2242.34
12.29+1.73
ERGNN rbb
64.0418.59 14.74:8.64
58.70+2.48
13.10
ERGNN-mf
64.56-199.6
14.30+9.24
59.94+1.778
11.91
DyGrain
61.66+10.58
17.72+10042
58.1542.49
14,07+1.80
IncreGNNN
10.75
17.22+10.60
58.37+2.41
14.01
SSM
69.83:13.16
8.10+2.81
61.1512.65
8.93
SSRM
64.77-8.34
14.2148.93
59.4711..77
12.23-11.72
TACO
70.37-12.70
7.64:12.43
62.5911.511
7.52
F.2 Graph coarsening methods
We present the trade-offs in terms of all matrices of TACO with its graph coarsening module RePro replaced by five other widely used graph coarsening algorithms with GCN as the backbone GNN model in Table 7
25

---

Table 6: Performance comparison of node classification in terms of F1 and BACC with GIN three datasets (average over 10 trials). Standard deviation is denoted after +.
Dataset Method
F1-AP(%) 1 F1-AF (%) BACC-AP (%)
BACC-AF (%)
joint train
84.39:0.84
0.35+t0.4
77.1740.83
1.45=1.07
finetune
64.92110:26
20.24:10.77
61.81
17.9115.22
simple-reg
65.04=10.74
20.04+:1..13
62.95+4.116
16.62+t5.14
EWC
75.73+14.74
9.36++5.01
69.3442.84
10.07+33.47
TWP
76.141:..35
9.14:14.72
69.1213.006
10,4913.51
OTG
65.18:19.97
20.08-110:29
61.98:14.79
17.7015.33
Kindle
GEM
72.10:1..29
12.4016.80
66.7612.92
12.05
ERGNN-rS
73.67=3.222
10.83+3.84
66.72+3.00
11.84+3.40
ERGNN-rb
70.25+7.35
84.39
65.53+3.14
13.70
ERGNN-mi
72.33=66.10
12.47=6.64
67.12+3.17
12.28+4.27
DyGrain
64.50-10.18
10.78
61.55:14.45
18.13-15.36
IncreGNN
65.38
19.6919.99
61.71155002
17.65
SSM
76.47:13.37
8.01
67.7842.84
10.73-13.03
SSRM
73.75=:3.25
10.79:3.56
66.55+3.22
12.07=3.63
TACO
78.71=11.76
6.44+1880
18.76:+186
8.28=12.13
joint train
84.42.+:.477
1.63+40.28
77.69
2.65++0.68
finetune
65.48=11.96
22.85+11.22
44.59
19.65+
simple-reg
66.84:19.64
21.8518.97
65.0413.77
19.761
EWC
77.45+7.06
10.79+66554
71.57+5.118
42.59
TWP
77.59++4.91
10.64+4.44
71.45++4.11
12.75+3.81
OTG
66.37=10.66
22.11+9..3
64.62+4.199
19.77
DBLP
GEM
78.71114.45
9.10.13.47
72.24113.86
11.3913.27
ERGNN-rS
76.63-13.94
11.4713.29
70.4513.51
13.6713.118
ERGNN-rb
73.23:17.29
14.77-6.50
68.7911.552
15.22.13.91
ERGNN- mf
75.96=55.74
12.1444.99
70.74+3.55
13.39+33.10
DyGrain
16.89=10.10
21.35+9.36
65.0643.77
19.10=2.51
IncreGNN
67.81=9.09
20.56:18.34
65.5813.66
18.68+2.79
SSM
80.21-17.85
6.74+17.29
73.96+5.116
8.24+14.99
SSRM
76.60+t4.89
11.55+44.30
70.89+4.29
13.30+3..0
TACO
84.03-+2.08
3.12+-0.89
78.09+2.19
1.38
joint train
71.86+11.54
2.99+L0.74
62.65+1.117
2.98+11.60
finetune
57.2019.033
20.3118.97
53.5011.44
16.1412.557
simple-reg
57.86+19.27
19.52+9.02
53.99+3.41
15.95
EWC
65.18
12.06.15.68
58.6411..78
10.90
TWP
65.45.15.56
11.72.5.35
58.76.11.78
10.63
OTG
58.24:19.38
19.3719.24
54.2311..35
15.46112.31
ACM
GEM
65.03=3..71
11.69:3.15
56,9413.43
11.65
ERGNN-
61.30
15.7747.57
55.87+2.68
13.30+2.11
ERGNN
61.12+8.25
16.10:8.07
55.82+2.60
1..81
ERGNN-mf
61.86-17.85
15.4947.73
56.76+4.84
13.10
DyGrain
58.09-+9.46
19.43+9.27
54.26++3.06
15.36+2.445
IncreGNNN
58.21+99.17
19.43+9.03
54.10+3.15
15.78+22.03
SSM
65.731:3.15
10.64:2.79
56.8112.58
11.1943.01
SSRM
61.47:17.38
15.6817.14
56.0912.64
13.02-11.55
TACO
67.1913.112
9.73112.8
59.06:12.40
9.13
G Additional ablation studies and analysis
G.1 Short-term forgetting
The average forgetting (AF) measures the decline in model performance after learning all tasks, which only captures the assess the model's long-term forgetting behavior. To evaluate the short-term forgetting of the model, introduce new metric, termed "short-term average forgetting" (AF-st),
26

---

Table 7: Coarsen runtime and trade-offs of TACO variations with different coarsening methods three datasets with GCN (average over 10 trials). Boldface indicates the best result of each column.
Dataset Method
Time (s) + TAFI-AP + TAFI-AF + TABACC-AP + TABACC-AF
Alge. JC
0.74
0.69
1.17
1.02
Aff. GS
7.88
14.48
12.08
Kindle
Var. neigh.
6.9
0.59
0.54
0.97
0.85
Var. edges
10.1
0.77
0.70
1.23
1.08
FGC
7.7
0.63
0.58
1.00
0.88
RePro
0.17
0.15
0.24
0.22
Alge. JC
70.8
4.08
3.90
5.65
5.20
Aff. GS
237.1
14.42
20.89
20.74
DBLP
Var. neigh.
7.3
0.43
0.41
0.55
0.50
Var. edges
28.0
1,63
1.53
1.98
1.77
FGC
10.8
0.64
0.61
0.83
0.76
RePro
0.07
0.06
0.08
0.07
Alge. JC
11.8
1.19
1.17
1.58
1.45
Aff. GS
96.1
12.29
12.5
16.07
15.4
ACM
Var. neigh.
10.3
1.58
1.61
1.82
1.79
Var. edges
13.8
1.24
1.20
1.65
1,50
FGC
7.0
1.05
1.06
1.15
1.11
RePro
1.4
0.13
0.13
0.19
0.17
with NFP
w/o NFP
kindle
DBLP
ACM
75
84
84
70
F1 (%)
BACC (%)
F1 (%)
BACC (%)
F1 (%)
BACC (%)
Figure 6: Average performance of the TACO with and without Node Fidelity Preserving (NFP).
which measure the decline in model performance on the most recent task when it learns new one:
AF-st
Σ 0--15-1 0jz-1- T 1=2
1
where the total number of task, and 0z.j is the prediction metric of model on test set of task after it is trained task i. We report the AF-st in terms of F1 score with GCN backbone three datasets in Table g
G.2 Shorter time interval
We investigate the performance of TACO and other baselines when each task is assigned with shorter time interval. For the DBLP and ACM datasets, we divided them into one-year time intervals, resulting total of 20 tasks. We have included the AP-fl and AF-fl 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 slight decline in performance, but TACO continues to outperform the other baseline models.
G.3 Efficiency Analysis
We analyze the efficiency of TA and other experience-replay-bee 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
27

---

Table 8: The averaged short-term forgetting in terms of F1 score (%) with GCN as the backbone three datasets (averaged over 10 trials).
Method
Kindle DBLP
ACM
joint train
0.33
0.37
0.69
finetune
33.15
22.25
19.57
simple-reg
29.91
19.39
19.07
EWC
22.92
13.34
15.68
TWP
21.25
14.19
15.47
OTG
32.89
20.67
19.45
GEM
17.43
9.25
10.95
ERGNN-rS
10.42
8.07
10.23
ERGNN-rb
15.78
9.30
12.72
ERGNN-mf
13.95
8.72
13.72
DyGrain
32.76
20.52
19.67
IncreGNN
32.85
21.42
19.68
SSM
12.18
5.15
10.26
SSRM
9.68
8.32
10.51
TACO
10.26
0.18
6.44
Table 9: Node classification performance with GCN as the backbone on two datasets (averaged over 10 trials) with shorter time intervals and more tasks. Standard deviation is denoted after +.
DBLP
ACM
Method
FI-AP(%)
FI-AF (%)
FI-AP (%) FI-AF (%)
joint train
84.38
11.99
1.60
+0.22
73.70
10.71 3.04
10.54
finetune
66.05
11.30
22.45
10.62
60.16
+8.58 19.56
+8.92
simple-reg
67.25
+7.80
21.50
16.86
58.44
17.62
21.10
47.87
EWC
79.04
+.6.5
8.84
+5.64
66.85
+4.66 11.77
+4.72
TWP
79.35
+.5.83
8.56
+5.41
66.52
+4.50 12.15 +4.64
OTG
67.45
+.8.1
21.03
+7.33
60.28
+8.18 19.54
+8.38
GEM
79.43
13.66
8.41
12.44
67.76
13.01 10.58
13.32
ERGNN-IS
75.08
16.32
13.13
15.48
61.43
17.76 17.64
18.16
ERGNN-rb
71.85
17.55
16.46
16.51
61.23
17.67 18.09
47.72
ERGNN-mf
74.24
+6.50
13.94
+5.37
63.13
#6.61 16.22
+6.83
DyGrain
67.96
19.19
20.58
+8.35
61.12
18.14 1851
#8.5
IncreGNN
66.19
+7.88
22.34
+7.31
60.53
+842 19.08
=8.70
SSM
82.08
+1.99
4.37
+1.12
67.22
+1.95 10.63
+2.30
SSRM
75.35
+6.14
12.95
+.5.19
62.11
+7.61
17.09
47.91
TACO
83.06
+2.25
4.18
+1.69
68.3
+3.21
10.17
+3.63
28

---

rS
rb
mf
kindle
DBLP
ACM
90
90
80
70
70
70
60
(%)
(%)
(%)
(%)
(%)
BACC (%)
Figure 7: Average performance of the TACO with different node sampling strategies: Reservior- Sampling (rs), Ring Buffer (rb), and Mean Feature (mf).
joint train
350
joint, Train
1200
joRtirain
reservoor
ER_ reseevivr
1000
reserviirr
SSM
:50
SSRM
SSAM
Mamort (M90
800
Memory
TACO
Memory
200
TACO
600
100-
400
50
200
Task
(a) Kindle
(b) DBLP
(c) ACM
Figure Memory usages different methods over tasks.
usage of the model (including the memory to store data for current task and the memory buffer to store information of previous tasks) for each task in Table TO We find that on average, SSM uses less memory than TACO on the Kindle dataset. However, on the DBLP and ACM datasets, SSM's memory usage is either more or similar. It's important to note that SSM maintains a sparsified graph that expands additional tasks introduced. As result, SSM's memory continues to grow with the increasing number of tasks. contrast, TACO, with its dynamic coarsening algorithm, consistently maintains relatively stable memory regardless of the number of tasks.
G.4 Node Fidelity Preservation
We investigate the effectiveness of the Node Fidelity Preservation strategy by removing it from TACO and compare the average performance of the variant of TACO with its default version. We report the average performance of the model on the three datasets in Figure We observe that DBLP dateset, the application of Node Fidelity Preservation improves the performance, while on the other two datasets, the model performs comparably marginally better without Node Fidelity Preservation. Note that our proposal of Node Fidelity Preservation is intended as a preventative measure, not as means of enhancing model performance. Node Fidelity Preservation aims prevent the situation
Table 10: The averaged memory usage (MB) for each task of experience-replaa--bseed methods.
Method
Kindle DBLP ACM
ERGNN-rS
49.5
38.0
121.1
ERGNN-rb
48.5
37.5
119,4
ERGNN-mf
48.5
37.6
119.5
DyGrain
47.9
37.1
118.1
IncreGNN
47.9
37.1
118.1
SSM
53.9
48.3
144.1
SSRM
50.0
38.4
122.6
TACO
59.0
41.9
144.4
29

---

Table 11: Statisties of datasets. "Interval" indicates the length of the time interval for each task. "# Item" indicates the total number of items/papers in each dataset.
Dataset
#Class
#Task #Class task #Items
cora
2/3
2,708
coauthor-cs
15
5
3
18,333
corafull
70
10
7
19,793
where minority classes vanish from the reduced graph due to unbalanced class distribution. Therefore, the improvement may not 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.
G.5 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 TACO with different node sampling strategies, Reservior-Sane -aapplin,,,m,iing. Ring Buffer, and Mean Feature on the three datasets in Figure It shows that TACO achieves better performance with Deservior-Sampling deduce that it is caused by the fact that Ring Buffer operates first in, first out (FIFO) basis, that it only retains the most recent samples for each class, making it fail to preserve information from distant past.
and Mean Feature. We
G.6 Performance on traditional class-incremental learning setup
We also evaluate TACO on traditional class-incrementa. learning setup prove its generability. We conduct experiments on three commonly used datasets in GCL literature including cora, coauthor-cs, and corafull. The details about their statistics and splitting are provided in Table [T] The performance of TACO with GCN as backbone in comparison with other baselines is provided in Table [2] which shows that forgetting could be more severe when tasks share non-overlapping class sets, and PO's ss rule on alleviating the forgetting is more evidently demonstrated.
30

---

Table 12: Node classification performance in terms of FI and BACC with GCN on three datasets under task-IL settings (average over 10 trials). Standard deviation is denoted after +.
Dataset
Method
F1-AP (%)
FI-AF (%)
BACC-AP (%) BACC-AF (%)
joint train
12.
5.9740.74
73.6842.23
9.98=0.83
finetune
32.59+1.32
61.05+1.74
31.85+0.95
60.92=1.50
simple-reg
39.11+4.75
54.30+4.86
37.1244.48
55.18=4.75
EWC
32.13+0.80
61.32+1.31
31.33+0.55
60.93=1.15
TWP
33.34+1.85
60.02+1185
32.29*1.74
59.92#1.69
OTG
30.4620.42
61.6840.62
30.0920.39
61.1820.76
cora
GEM
57.8642.42
34.1542.42
50.5042.81
39.09=3.02
ERGNN-rS
74.48+2.55
14.93+2.53
65.59+2.36
19.92=2.18
ERGNN-rb
69.05=1.81
21.49+1.60
61.62+1.97
25.76=1.80
ERGNN-mf
69.11+1.34
21.38+1.53
61.84+1.42
25.59=1.47
DyGrain
32.83+1.87
60.81+1.97
31.94+1.35
60.78
IncreGNN
32.57+1.33
60.85+1.57
31.65+1.04
60.63#1.31
SSM
59.6145.66
29. 29.9445.38
18.1445.31
37.05=4.83
SSRM
75.16+1.38
14.17=1.65
66.15:1144
19,48=1.70
TACO
78.16+1.29
9.69=1.35
67.75*1.25
14.38
joint train
92.30+0.24
3.11+0.31
86.43+0.61
5.55+0.45
finetune
20.1620.37
77.07=0.41
20.30=1.03
75.68=0.95
simple-reg
24.88+1.54
72.01+1.44 .66
22.98+1.42
71.68+1.38
EWC
48.47+7.07
41.84+8.61
36.41=5.12
46.56#6.51
TWP
45.45+11.11
38.5949.56
33.0149.46
42.5829.48
OTG
19.9240.05
77.0640.12
19.8340.09
75.9920.21
coauthor-cs
GEM
69.5944.54
26.61+4.45
62.81+4.64
31.26+4.47
ERGNN-rs
64.75+4.34
31.02+4.49
56.29+4.99
36,89=5.09
ERGNN-rb
62.18+3.05
34.13+3.15
59.95+2.78
34.17+2.92
ERGNN-In mf
46.1645.51
50.46+5.46
45.75+4.28
49.06t4.27
DyGrain
23.6246.34
70.43+10.61
21.2643.35
69.56+10.47
IncreGNN
25.3048.82
71.03+9.61
23.77+7.43
70.48+7.76
SSM
59.87+3.89
35.45+3.97
48.26+2.97
43.56+2.36
SSRM
30.9143.09
65.8543.21
28.2642.79
66.71+3.03
TACO
92.8420.85
2.2220.76
87.24+1.72
3,39+1.56
joint train
74.33+0.48
4.00+0.50
58.9440.61
6.96#0.77
finetune
7.24+0.35
76.53+0.57
6.35+0.29
72.52+0.76
simple-reg
11.18+2.10
66.65+3.13
8.01+1.25
61 61.04=2.70
EWC
20.47+5.27
60.30+4.66
13.45+3.17
60. 10.1843.11 14
TWP
19.7943.28
61.3043.55
13.30+2.14
60.51+2.46
OTG
7.43+0.36
77.26+0.61
6.54+0.37
73.19
corafull
GEM
26.1746.79
58.9246.57
16.43+4.35
62.33+4.23
ERGNN rs
23.82+3.88
59.97+4.24
15.11+2.48
60.57=3.05
ERGNN-rt rb
18.8242.59
65.29+3.02
15.28
61,87+2.85
ERGNN-mn mf
19.1942.54
65.29+2.36
15.28
18.
DyGrain
7.42+0.31
77.03+0.50
6.54+0.25
73.10=0.60
IncreGNN
7.58+0.24
77.18+0.51
6.69+0.24
73.20=0.84
SSM
45.77+1.76
35.59+1.85
32.37+1.60
38.53+1.73
SSRM
22.46:2.99
61.2242.73
14.11+1.93
61.42+1.88
TACO
55.7441.13
17.14+1.13
39.50=1.08
18.1320.81
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope, demonstrated through both theoretical analysis and empirical study.
Justification:
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We include a separate section in the paper to discuss the limitations of our
works.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide the full set of assumptions and complete (and correct) proof for each theoretical result.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper provides all necessary implementation details, including pseudocode, to reproduce the main experimental results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We submit source code, data, and comprehensive instructions to faithfully reproduce the main experimental results.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide all the training and test details in Appendix
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report standard deviation and p-values to demonstrate statistical signifi- cance.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed reproduce the experiments?
Question:
32

---

Answer: [Yes]
Justification: We provide information about the GPU used for the experiments and also report and analyze memory and time usage.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:/ppsw.paappp...ooooo/ococca
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics and confirm the research conducted in the paper conforms with it.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss the positive social impact of this work separate section and do not foresee any negative social impact.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We use open-source datasets and properly cite them.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We submit zip file containing the code for proposed method, along with detailed implementation instructions.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subjects were involved in the research conducted in this paper.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No human subjects were involved in the research conducted in this paper.
33


Reviews:
[{"review_id": "dTqP0abR1u", "reviewer": "Reviewer_HprJ", "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.\n\nExperiments are conducted on three datasets against multiple SOTA baselines.", "questions": "1. graph coarsening will incur extra computation. will this result in significant extra resource consumption.\n\n2. subgraph rehearsal methods also exist, can they also preserve the topology? What is the advantage of the proposed method?", "limitations": "As mentioned by the authors, this paper does not cover the scenario in which nodes and edges can be deleted or modified.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Continual learning of graph neural network is practically important and largely overlooked.\n\nThis paper proposes a coarsening based method for preserving the topological information while maintaining a tractable memory consumption, which is novel.\n\nEmpircal results are promising. The proposed method consistently outperform baselines.", "weaknesses": "It is unclear how the adopted datasets split into different tasks. \n\nIt seems that fintune also works well on the three adopted datasets, maybe this indicates that the adopted datasets and tasks are not challenging enough.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback. We are happy to address your concerns and questions. Detailed responses to your comments are provided below.  \n\n---\n\n## W1. How to split datasets into different tasks\n**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.** \n\n ---\n\n## W2. Fine-tuning results and challenges of the tasks \n\n**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.  \n\nNevertheless, we consider the nearly 20% forgetting reported in our setting is significant and worth studying.  \n\n* **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. \n\n* **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. \n\nAdditionally, 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.  \n\n[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. \n\n ---\n\n## Q1. Extra computation of graph coarsening  \n\n**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. \n\n ---\n\n## Q2. Comparison with subgraph rehearsal method \n\n**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”*.  \n\nWe 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. \n\n**To better demonstrate the advantages of our method, we also provide a table comparing the characteristics of different methods in the attached PDF file.** \n\n[1] Zhang, X., Song, D., Chen, Y., & Tao, D. (2024). Topology-aware Embedding Memory for Learning on Expanding Graphs. arXiv preprint arXiv:2401.03077.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KPnPSuXdc7", "reviewer": "Reviewer_F1Ar", "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.", "questions": "1. The full name of GCL is not explicit defined.\n2. In the Combine step, graphs are combined using a hash table. Are the graphs labeled?\n3. Graph pooling is highly related to graph coarsening. Why not add some comparisons with graph pooling methods?\n4. At each timestamp, the model only aggregate information from last timestamp. Then what is preventing the model from forgetting information happened long ago?", "limitations": "yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The introduction of a topology-aware coarsening approach specifically for continual learning in GNNs is innovative and addresses a significant problem in the field. The paper presents a well-defined methodology with clear steps for combining, reducing, and generating graphs, which enhances the reproducibility of the approach. Extensive experiments and comparisons with state-of-the-art methods demonstrate the efficacy of TACO, providing strong empirical support for the proposed framework. Additionally, by focusing on reducing the graph size, the framework offers a scalable solution that can handle the growing size of real-world graphs in continual learning scenarios.", "weaknesses": "The choice of baseline methods for comparison might not cover all recent advances in continual learning and graph coarsening, potentially overlooking some relevant techniques.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback! We are happy to address your concerns and questions. Detailed responses to your comments are provided below. \n\n---\n\n## W1. Additional related studies \n\n**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.   \n\n---\n\n## Q1. Full name of CGL \n\n**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.  \n\n ---\n\n## Q2. Clarification of combine step \n\n**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 \nkeeps 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. \n\n ---\n\n## Q3. Comparison with graph pooling \n\n**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.** \n\nTwo major categories of hierarchical pooling methods are often used: node dropping and node clustering. \n\n- **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. \n\n- **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. **\n\nThere 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. \n\nWe 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. \n\n[1] Zhang, M., & Li, P. (2022). Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities. arXiv preprint arXiv:2204.07321.  \n\n[2] Ying, R., You, J., Morris, C., Ren, X., Hamilton, W., & Leskovec, J. (2018). Hierarchical Graph Representation Learning with Differentiable Pooling.  \n\n[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.  \n\n[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.  \n\n ---\n\n## Q4. Preservation of knowledge from long time ago \n\n**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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vlBF8oJgsc", "reviewer": "Reviewer_AUFc", "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.", "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?\n2. 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? \n3. 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. \n4. In the replay buffer did you only keep the nodes or also their neighborhood structures?\n5. 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.\n6. I am wondering how large the original subgraphs are at each time step and whether their sizes affect the performance?\n7. 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. \n\n\n[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. \n[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. \n[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": "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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1.The paper is well written and easy to read \n\n2. The paper introduces a novel method incorporating the graph coarsening method into the continual learning framework.  \n\n3. The experiments demonstrate the effectiveness of the proposed method.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback. We are happy to address your concerns and questions. Detailed responses to your comments are provided below. \n\n---\n\n## Q1. Clarification on the setting of task splitting  \n\n**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. \n\n ---\n\n## Q2, Limitations. Additional related work on benchmarking / different CGL setting \n\n**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. \n\nWe 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.** \n\n---\n\n## Q3, Q7. Small numbers of classes/new classes  \n\n**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. \n\n---\n\n## Q4. Replay buffer \n\n**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. \n\n---\n\n## Q5. Ablation study on replay buffer  \n\n**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.**\n\n**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. \n\n ---\n\n## Q6. Task size / smaller tasks \n\n**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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eKOqNQdKF9", "reviewer": "Reviewer_AYqY", "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.", "questions": "1.\tIn 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.\n\n2.\tThe 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.\n\n3.\tWhen 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?\n\n4.\tThe section 4.4.3 is very confusing. The authors should rephrase this part to make it easier to understand.\n\n5.\tThe authors should further include an ablation study to investigate the overall performance of TACO with different reduction rates.\n\n6.\tThe authors are encouraged to include descriptions of other graph coarsening methods used in the paper.\n\n7.\tThe information of some references is incomplete such as [47] and [54] in the reference section.\n\n[1] Liu, Yilun, Qiu,Ruihong, & Huang, Zi. 2023b. CaT: Balanced Continual Graph Learning with Graph Condensation. In: Proc. of ICDM.\n\n[2] Niu, Chaoxi, Guansong Pang, and Ling Chen. \"Graph Continual Learning with Debiased Lossless Memory Replay.\" arXiv preprint arXiv:2404.10984 (2024).", "limitations": "The authors have discussed the limitations and societal impacts of the proposed method which are adequate.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The proposed method TACO coarsens the previous graphs into the memory buffer for replaying while preserving the graph topology.\n\nThe memory buffer constructed by TACO can maintain a stable size when sequentially learning new tasks\n\nThe proposed method's effectiveness is supported by rich experimental results", "weaknesses": "The paper is not well structured, and some statements are confusing.\n\nThe authors are encouraged to have a more complete comparison to better validate their proposed method.\n\nSome important existing works are missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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. \n\n---\n\n## W1. The paper is not well structured \n\n**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.  \n\n ---\n\n## W2, W3, Q2. Additional literature review/baselines \n\n**A:** We have conducted additional literature review and compared with more baseline. Please refer to our global response.   \n\n ---\n\n## Q1. Lack of discussion of related work \n\n**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. \n\n ---\n\n## Q3. The reasoning behind using GNN embedding for calculating similarity \n\n**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.  \n\n---\n\n## Q4. Section 4.4.3 is confusing \n\n**A:** Thank you for pointing it out. We will rephrase this section as follows:  \n\n> “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.” \n\n---\n\n## Q5. Performance of TACO on different ratio rates  \n\n**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. \n\nBesides, 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. \n\n ---\n\n## Q6. Description of graph coarsening methods\n\n**A:** Thank you for the suggestions. **We provide summaries of graph coarsening methods and their limitations in Appendix A.2** due to page limit.  \n\nBesides, we will further provide a more detailed description of the baseline graph coarsening methods as follows: \n\n> 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. \n> - **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. \n> - **Aff. GS** uses affinity, a normalized relaxation-based node proximity heuristic, during the aggregation process, merging nodes with higher affinity scores. \n> - **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.\n\n> Above approaches result in high computational complexity and rely solely on graph structures, ignoring node features. \n> - **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. \n ---\n\n## Q7. Incomplete information in paper references  \n\nQ7. We will fix this and make sure all references are correctly formatted in our revised version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We appreciate the thorough reviews provided for our paper. We are encouraged by the positive comments. **All four reviewers recognize the novelty of our work.  They also concur that our extensive experimental evaluation serves as strong evidence to support the effectiveness of our method. Additionally, two reviewers (F1Ar, AUFc) acknowledge that our paper is well-written, with a clear description of the methodology.**

We are keen to address the concerns and questions of the reviewers and provide detailed responses to every point raised. Please refer to our responses to individual reviewers. 

We summarize the common concerns raised by the reviewers and how we address them as follows. New results are also provided in response to some of the concerns. 

* We have added the two important related studies suggested by Reviewer F1Ar. Additionally, we conducted an extensive literature review and identified some other recent work. **To the best of our knowledge, by including these additional methods, our literature review is comprehensive and covers the most advanced experience-replay-based CGL methods.** However, we are happy to include any relevant studies suggested by the reviewers. 

* We have implemented two additional related methods which have open-source code and reported the new results (see attached PDF). 

* To better demonstrate our contribution and position our method within the literature, we have provided a table that compares the characteristics of our method with other experience replay-based methods, including the newly added ones (see attached PDF). 

In the attached PDF, we include: 

* New results on two new baselines CGL methods. (**Table 1**) 

* Comparison between different experience-replay-based CGL methods. (**Table 2**) 

* Performance of TACO with different reduction rates. (**Figure 1**) 

---

## Additional related work on CGL 

We appreciate reviewers AYqY and F1Ar for pointing out some missing related work as comparison methods in CGL. Following reviewer F1Ar's suggestion, we have included the two most up-to-date experience replay-based methods [1][2] in our comparison.  

- **CaT** [1] uses a condensed graph as the memory buffer and employs a "Training in Memory" scheme that directly learns on the memory buffer to alleviate the data imbalance problem. However, the condensed graph contains only sampled nodes with self-loops, resulting in the loss of valuable topology information. 

- **DeLoMe** [2] stores the learned representations of the sampled nodes as a memory store, which can preserve graph structure information. However, it still cannot handle inter-task edges, and the stored representations are inadequate for dealing with the dynamic receptive field of old nodes when new nodes form connections with them. 

Besides, we also find other two recent studies that are worth mentioning including **SEM-curvative** [3] and  **PGDNN** [4]. They all provide unique insights into storing useful information from previous tasks.  

We conducted additional experiments to evaluate the **CaT** and **DeLoMe**, and the results are reported in **Table 2** in the attached PDF. We are not able to implement **SEM-curvative**  and **PGDNN** as their source code is not available.  

We will incorporate the above discussion and the new results in the revised version. 

[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). 

[3] Zhang, X., Song, D., & Tao, D. (2023). Ricci Curvature-Based Graph Sparsification for Continual Graph Representation Learning. IEEE Transactions on Neural Networks and Learning Systems. 

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

 ---

## The Contribution of TACO 

To better highlight the advantages of our proposed method, we provide a comparison between our method and these experience-based methods in **Table 2** in the attached PDF file. **Our method, TACO, is the only one that can preserve graph topology, handle inter-task edges, and consider the growing receptive field of old nodes.**

Meta-review: 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.
Decision: Accept (poster)