AGALE: A Graph-Aware Continual Learning Evaluation Framework
Authors: Tianqi Zhao
Alan Hanjalic
Megha Khosla
Venue: Accepted by TMLR ()

Abstract: In recent years, continual learning (CL) techniques have made significant progress in learning from streaming data while preserving knowledge across sequential tasks, particularly in the realm of euclidean data. To foster fair evaluation and recognize challenges in CL settings, several evaluation frameworks have been proposed, focusing mainly on the single- and multi-label classification task on euclidean data. However, these evaluation frameworks are not trivially applicable when the input data is graph-structured, as they do not consider the topological structure inherent in graphs. Existing continual graph learning (CGL) evaluation frameworks have predominantly focussed on single-label scenarios in the node classification (NC) task. This focus has overlooked the complexities of multi-label scenarios, where nodes may exhibit affiliations with multiple labels, simultaneously participating in multiple tasks. We develop a graph-aware evaluation (AGALE) framework that accommodates both single-labeled and multi-labeled nodes, addressing the limitations of previous evaluation frameworks. In particular, we define new incremental settings and devise data partitioning algorithms tailored to CGL datasets. We perform extensive experiments comparing methods from the domains of continual learning, continual graph learning, and dynamic graph learning (DGL). We theoretically analyze \agale and provide new insights about the role of homophily in the performance of compared methods. We release our framework at https://github.com/Tianqi-py/AGALE.

Published in Transactions on Machine Learning Research (Ju2e/2024)
AGALE:
A Graph-Aware Continual Learning Evaluation
Framework
Tianqi Zhao
TZhao-1@tudelft.nt
Delft University of Technology Delft, Netherlands
Alan Hanjalic
A.Hanjale@tuueeff.tl
Delft University of Technology
Delft, Netherlands
Megha Khosla
M.Kholla@tudelff.l
Delft University of Technology
Delft, Netherlands
Reviewed on /ttp://eww...t//////////a/////tr
Abstract
In recent years, continual learning (CL) techniques have made significant progress in learning from streaming data while preserving knowledge across sequential tasks, particularly in the realm of euclidean data. To foster fair evaluation and recognize challenges in CL settings. several evaluation frameworks have been proposed, focusing mainly on the single- and multi-label classification task on euclidean data. However, these evaluation frameworks are not trivially applicable when the input data is graph-structured, as they do not consider the topological structure inherent in graphs. Existing continual graph learning (CGL) evaluation frameworks have predominantly fo- cused single-label scenarios in the node classification (NC) task. This focus has overlooked the complexities of multi-label scenarios, where nodes may exhibit affiliations with multiple labels, simultaneously participating in multiple tasks. We develop graph-aware evaluation (AGALE) framework that accommodates both single-labeled and multi-labeled nodes, addressing the limi- lations of previous evaluation frameworks. particular, we define new incremental settings and devise data partitioning algorithms tailored CGL datasets. We perform extensive experiments comparing methods from the domains of continual learning, continual graph learning, and dy- namic graph learning (DGL). We theoretically analyze AGALE and provide new insights about the role of homophily in the performance of compared methods. We release our framework at https: //github/
1 Introduction
Continual Learning (CL) describes the process by which a model accumulates knowledge from a sequence of tasks while facing the formidable challenge of preserving acquired knowledge amidst data loss from prior tasks. finds application in several fields, such the domain of medical image analysis, where model has to detect timely emerging new diseases in images while maintaining the accuracy of diagnosing the diseases that have been encountered in the past. Significant achievements have been made CL for euclidean data domains such images and text [Aljundi]
et al. 2018 Parisi et al. 2018 Tang & Matteson 2021 Hadsell et al. 2020 Van de Ven & Tollas 2019). Recent works
have also delved into the broader scenario of multi-label continual learning (MLCL) (Wang et al. 2020b 2021 Liu
et al. 2022
Wei et al. 2021 where one instance can be simultancously associated with multiple labels.
settings, several evaluation frameworks (Farquhar Gal 2019 Lange et al. (0023) have been proposed, focusing on the single- and multi-label classification task on the euclidean data. However, these frameworks are not trivially applicable to graph-structured data due to the complexities arising
foster fair evaluation and identify new challenges

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
from interconnections and multi--abel nodes within graphs. Besides, existing evaluation frameworks in continual graph learning (CGL) (Ko et al. 2022 Zhang et al. 2022) evaluate the node classification task in the setting of associating nodes with single label (which we refer to as the single-label scenario), thereby overlooking the possibility for nodes from previous tasks to adopt different labels in new tasks or acquire additional labels with time. For instance, in the context of a dynamically evolving social nelwork, not only can new users with diverse interests (labels) be introduced over time, but existing users may also lose old labels or accumulate new labels continuously.
To illustrate the limitations of current CL evaluation frameworks when considering the multi-label scenario in graphs, we start with example of a multi-label graph as in Figure [ We use color coding to indicate the classes the nodes belong to. Please note that in what follows, we employ the term "class" to refer to the classes that correspond to a task. To refer to a class assigned to a particular node we use the term "label".
Node 2
Node
Node
1.1 Limitations of current continual learning evaluation frameworks
Node 4
Node
Lack of graph-aware data partitioning strategies. Current experimental setups typically simulate continual learning settings by employing certain data partitioning methods over static data. However, existing CGL frameworks do not consider the multi-label scenario in the data partitioning algorithms.
Figure 1: An example multi- label graph with colors indi- cating to the different node labels.
The multi-label continual learning evaluation framework for Euclidean data (Kim et al. 2020a) suggest the use of hierarchical clustering techniques, which involves grouping classes into a single task based on their co-occurrence frequency and subsequently eliminating instances with label sets that do not align with any class groups Applying such a technique to graph-structured data not only risks excluding nodes with a higher number of labels but also disrupts the associated topological structures.
In Figure 2 we illustrate application of the existing MLCL framework the multi- label graph depicted in Figure The classes blue, green, and red are collectively treated as one task due to their frequent co-occurrence. Node 3, having the maximum number of labels, is removed from the graph since no task encompasses all its labels. It is noteworthy that employing hicrarchical clustering techniques increases the likelihood of eliminating nodes with more labels, effectively reducing both the number of multi- labeled nodes and the associated topological structure. In the current example, proper training and testing of the model on the red class is hindered, as only node remains in the subgraph with the label red. Besides, node 5 becomes isolated in the second subgraph.
Node 2
Node
Node 5
Figure 2: Subgraphs gener- ated by grouping frequently co-occurring classes as a task.
Generation of train/valltest sets. Furthermore, the data partitioning algorithm is also responsible for the division of each subgraph into training, validation, and test subsets. In Figure 3 we show an example of train/val/test subsets generated using the strategy adopted by previous CGL evaluation frameworks for the task of distinguishing between blue and green classes. In particular, nodes belonging to single class are divided independently at random into train/validation/uue sets, assuming no overlap between classes. However, when each node can belong to multiple classes, and random division within each class is not always feasible. For instance, the same node may serve as training data for one class and testing data for another in the same task, as is the case for node 1 in Figure 3 In this particular case, the model may observe the test data during the training process, resulting in data leakage. Conversely, considering the entire dataset as a whole for division would result in the dominance of the larger class, causing all nodes from the smaller class be aggregated into the same split and thereby under- mnder-representing the smaller class in the other split. For instance, in multi-label datasets such as YELP, two classes can exhibit complete overlap, where all nodes from the smaller class also belong to the larger class. In this scenario, if the nodes belonging to the larger class are split first, there might be no nodes left to make the required splits for the smaller class.
independent
Use of predefined class orders. Existing CGL evaluation frameworks rely on a single predefined class order the dataset and group sets of K classes as individual tasks. As the predefined order might not always reflect the true generation process of the data, it important evaluate CL models over several random class orders. Specifically for
2

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
multi-label scenarios, the employed class order may not only influence the nodes and their neighborhood structures presented at each time step but also affect the number of labels assigned to particular node in given task. We demonstrate in Figure | using nodes from the multi-label graph in Figure how distinct class orders generate subgraphs with the same set nodes but with different topologies and node label assignments.
Limitations on the number of tasks. Last but not least, previous CGL benchmarks typically predetermined the size of model's output units, assuming an approximate count classes in each graph during model initialization. However, this assumption is unrealistic because the eventual class size is often unknown, leading to potential inefficiencies in storage capacity overflow.
Node
Node 3
Train
Train Test
Node
Test Train
1.2 Our Contributions
To tackle the bhove-mentioned gaps, we develop generalized evaluation framework for continual graph learning, which is applicable both for multi-class and multi-label node classification tasks and can be easily adapted for multi-label graph and edge classification tasks. Our key contributions are as follows.
Figure 3: The split of the nodes within one subgraph generated by the previous CGL framework.
We define two generalized incremental settings for the node classification task in the CGL evaluation framework which are applicable for both multi-class and multi-label datasets.
We develop new data split algorithms for curating CGL datasets utilizing existing static benchmark graph datasets. We theoretically analyze the label homophily of the resulting subgraphs which is an important factor influencing the performance learning models over graphs.
We perform extensive experiments assess and compare the performance of well-established methods within the categories of Continual Learning (CI., Dynamic Graph Learning (DGL), and Continual Graph Learning (CGL). Through our analysis, we evaluate these methods in the context of their intended objectives, identifying their constraints and highlighting potential avenues for designing more effective models to tackle standard tasks in CGL.
We re-implement the compared models in our framework while adapting them for the unknown number of new tasks that may emerge in the future.
class order 1:
class order 2:
Node 2
Node
Node
Node
Node
Node 2
Node 3
Node
Node
Node
Node
Node
Node
Node
T2
T1
Figure 4: An example of subgraphs obtained by applying different class orders for the static multi-label graph in Figure
Problem Formulation
We start by providing a general formulation of the continual learning problem for graph-structured data and elaborate the additional complexities when the nodes in the graph may have multiple labels as compared to the single-label scenario.
3

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
Problem Setting and Notations. Given a time sequence T = (1.2..... T), at each time step T. the imput is one graph snapshot G. (V,, &t, x,, Yt), with node set V2 and edge set & Additionally, X, E RiVv and E {0, 1J1vixi, denote the feature matrix and the label matrix for the nodes in graph Gt, where D is the dimension of the feature vector, and C, is the set of classes seen/ genn/availbble at time t. We assume that the node set Vr is partially labeled, i.e, Vi = (%, Vr where V and V. represent the labeled nodes and the unlabeled nodes in Gr. We use A, to denote the adjacency matrix of We use y" to denote the complete label set of node v and VE to denote the label set of node observed at timet. t.
Objective. The key objective in CGL setting, as described above, is to predict the corresponding label matrix of Vi denoted by Y (when the complete label set is restricted to Ci) while maintaining the performance over the classification on nodes in all graphs in the past time steps in {1,21 11,2,...,, 111. 13.
2.1 Differences to single-label scenario
Having explained the problem setting and the objective we now describe the key differences of the multi-labe scenario as compared to the single-label case in continual graph learning, which were so far ignored by previous works resulting various limitations as illustrated in Section 1.1
Node overlaps in different tasks. In the single-label scenario each node is affiliated with one single class, exclusively contributing to one task. The following statement, which states that no node appears in more than one task, always holds:
Vi.j E T, and i * j.V,
(1)
However, in the multi-label scenario, one node can have multiple labels and can therefore participate in multiple tasks as time evolves. Contrary to the single-label scenario, when the nodes have multiple labels, there will exist at least a pair of tasks with at least one node in common as stated below.
j E T, and i * nV # 0
Growing label sets. In the single-label scenario, the label set of node y", stays the same across different time steps, i.c.,
Vi.j E T, TT =
(3)
However, in the multi-label scenario, the label set of node may grow over time, i.e., a node may not only appear in several tasks as above but also have different associated label sets, ie.. the following holds.
Bi,j E T, YF
(4)
Changing node neighborhoods. Note that while simulating continual learning scenario, subgraphs are curated corresponding to sets of classes/labels required to be distinguished in a particular task. In other words, the subgraph presented for a particular task only contains edges connecting nodes with the label set seen in that task. Therefore, the neighborhood of node v, denoted as N can also be different across different time steps in the multi-label scenario, i.e.,
Ri,j E T, Nº AN
In the multi-label graphs, both multi-label and single-label nodes exist, providing therefore a suitable context to develop generalized CGL evaluation framework as elaborated in the next section.
3 AGALE: our evaluation framework
We present a holistic continual learning evaluation framework for graph-structured input data, which we refer to AGALE (a graph-aware continual learning evaluation). We begin by developing two generalized incremental settings (in Section 3.1 that accommodate the requirements of the multi-label scenario (as discussed in Section 2.1 with respect to node overlaps in different tasks and growing label sets. In Section 3.2 we develop new data partitioning algorithms designed to derive subgraphs and training partitions from a static graph dataset, tailored specifically for the developed incremental settings. To underscore the significance of our approach, we provide theoretical analysis of AGALE in Section 3.3 and compare with the previously established CGL and MLCL frameworks in Section 3.4
4

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
Tesk-Increeeente Setting:
Cless-Incremental Setting:
Node
Node
Node
Node
Node
Node 2
Node
Node
Node
Node 5
Node
Node
T1
T2
T1
T2
T
Figure 5: Visualization of our proposed generalized evaluation CGL framework AGALE.
3.1 Two Generalized Incremental Settings for Continual Graph Learning
We first define and develop two generalized incremental settings in CGL, i.c., TASK-IL SETTING and CLASS-IL SETTING. In the TasK-IL SETTING, the goal is to distinguish between classes specific to each task. Different from single-label settings, the multi-labeled nodes can be present with non-overlapping subsets of their labels in different subgraphs, as shown in Figure Formally, for any node u in the multi-label graph, in the TASK-IL -IL SETTING we have
Vi,j E T.V ny = 0.
the CLASS-IL SETTING, the goal is to distinguish among all the classes that have been seen so far. Specifically, in addition the same node appearing multiple tasks in the previous setting, node with multiple labels can attain new labels as new tasks arrive, as shown in Figure Formally, for any node in the multi-label graph,
Vi.j E i,ifi <, then V c
Note that the above settings allow for node overlaps and growing/changing label sets of the same node at different time points.
3.2 Data Partitioning Algorithms
We describe our data partitioning algorithms to simulate sequential data from static graphs. The design strategy of our algorithms takes into account of the node overlaps in lasks, the nrowingcchangig label set of nodes over time, and the changing node neighborhoods while minimizing the loss of node labels and the graph's Ss topological structure during partitioning. Our developed data partition strategy can be employed in both incremental settings and consists of the following two main parts.
Task sequence and subgraph sequence generation. We employ Algorithm segment the provided graph from the dataset into coherent subgraph sequences. We first remove the classes with size smaller than threshold ö. Instead of using predefined class order (as discussed in Section 1.1 we generate random orders of the remaining classes to simulate the random emergence of new classes in the real world. Specifically, given dataset with C' classes, we group random classes as one task for one time step. At any time point f, let C, denote the set of classes grouped for the task at time We construct a subgraph G, = (V,, Ex) such that V, is the set nodes with one or more labels in C, The edge set &, consists of the induced edges on V. Note that the number of classes chosen to create dataset and subsequently catastrophic forgetting, choose K 2 in this work. If the dataset has uneven number of classes in total, the remaining last class will be grouped with the second last class group.
task is adaptable. In order maximize the length of the task sequence for each given graph
Construction of train/val/test sets. To overcome the current limitations of generating train/val/test sets discussed in Section 1.1 employ Algorithm to partition nodes of given graph snapshot G, For the given

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
subgraph Gz. our objective is to maintain the pre-established ratios for training, validation, and test data for both the task as whole and individual classes within the task. To achieve this, our procedure starts with the determination of the size of each class. Note that the cumulative sizes of these classes may exceed the overall number of nodes in the subgraph due to multi-labeled nodes being accounted for multiple times based on their respective labels. Subsequently, the classes are arranged in ascending order of size, starting with the smallest class. The smallest class partitioned in accordance with the predefined proportions. Subsequent classes in the order undergo partitioning with the following steps:
We identify nodes that have already been allocated to prior classes.
We then compute the remaining node counts for the training, validation, and test sets in accordance with the predefined proportions for the current class.
-Finally, we split randomly the remaining nodes within the current class into train/val/test sets such that their predefined proportions are respected.
Note that for given class order, the structural composition of each subgraph remains constant across both the incremental settings. What distinguishes these incremental settings is the label vector assigned to the nodes. Specifically, nodes with a single label manifest uniquely in one subgraph corresponding to a task. Conversely, nodes with multiple labels appear in the TAsK-IL SETTING with distinct non-overlapping subsets of their original label set across various subgraphs while appearing with the expansion of their label vectors in the CLASS-IL. SETTING.
Algorithm 1 Task Sequence and Subgraph Sequence Generation
Require: Static graph G = EV, with classes C = {c1, C2,.... cc), }. threshold of small classes ò, group size K Ensure: n task sequences S = S2,.., and for each task sequence S; a corresponding subgraph sequence G. (2,,92,.... |r}
1: for ej E C do
Ve, - {uilc E yi}
C' [C -
([C-cyIlVa cyllVoy <)
Generate random orders of C': O {01, O2..,, On)
5: for O₂ E O do
6: for | = 1 to [ T do
7:
Group the first & classes as a task: St = {ci,.... ck}
8:
0, = 0--S,
9:
Vi fuily; S s
10:
& (e(u,v)le
G. Ev)
In the Appendix A.11 we present an analysis of the subgraphs derived by AGALE from the given static graph in PCG as an example showcasing the efficacy of our approach.
3.3 Theoretical Analysis Of AGALE
As studied in previous works Ma et al. 2021 Zhao et al. 2023), the similarity of labels between neighboring nodes (usually termed label homophily) influences the performance of various graph machine learning algorithms for the task of node classification in the static case. We here provide a theoretical analysis of AGALE with respect to the label homophily of generated subgraphs under different conditions. We would later use our theoretical insights and the dataset properties to analyze the performance of various methods. We use the following definition of label homophily for multi-label graphs proposed Zhao al. (2023).
Definition Given a multi-label graph G, the label homophily h of is defined as the average of the Jaccard similarity of the label set of all connected nodes in the graph:
yd n y
h
(1J)EE

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
Algorithm 2 Train and Test Partition Algorithm Within One Subgraph
Require: subgraph Gr in subgraph sequence (91, $2.-..,9r7 ,r.,, proportion P for train, validation, and test P (Prrin Peat, Ptest)
Ensure: the split within subgraph G, (Vrrain Veat Viest) for task S;
1: Get the classes for the current task S; = (ci,...,
2: O' Sorlascena((4) (ey.l) for Cj. E St
3: initialize empty node set Virain, Vral and Vieat
4: initialize empty encountered nodes set V/
for C O' do
V. (v:lc y
if is the smallest class in S; then
Randomly split V. into ytrain, yeal plest according to P
8:
9:
else
Calculate the size of train/val/test set [Vtrain|, Deval, [Veeat according to Ddup- = V. Ve Ve-
10:
11:
13:
for E Vaup do for split E [Vtrain, Veal Vlest] do if o; in split then |split| = |split|
14:
15:
16:
for split [Vtrain, Veal Viest] do Randomly choose ( nodes from Ve to add to split add Vtrain, Veal Vleat to Verain yeal West
17:
18:
19:
20:
add V. to V;
Let for any two connected nodes i,j E V, n denotes the label homophily over the edge e(t, E E in graph G. We then have the following result about the label homophily of e(i. j) in the subgraph G, generated by AGALE time
e(i.))
(e(1 Theorem For any edge e(i,j) E E and any subgraph at time t, Sr such that e(i, j) E E,, hG. 2 h (lii)) when
least one of the nodes {i, single-labeled. For the case when both nodes i, are multi-labeled, we obtain e(,,)) with probubility at least (1 - - ne(s))) ) for TASK-Il. SETTING and (1 (1 - -ig (1 ) (t)) for CLASs-II.
e(5.)) > hig ng
SETTING.
Proof. In the multi-label graphs, one pair of connected nodes belongs to the following three scenarios: 1) two single- labeled nodes are connected, 2) a single-label node is connected to a multi-labeled node, and 3) two multi-labeled nodes are connected.
Scenario 1: Note that any time step two nodes i and connected if and only if at least one label for each node appears in C, As in the first scenario, both the nodes single-labeled, and the label homophily score for edge j(i,j) stays the same in the subgraph in the original graph:
0,
if + yd if y
((ii) e((i)) hg. hg
1,
Scenario 2: In the second scenario, where one single-labeled node i is connected to multi-labeled node j. at any time step when j(,,j) appears in the subgraph Gr.
hgg
p(t,]
e(id)) 11g
= 0,
if $ y
c(i.)) a(ks) hg. 2 l1g
1.
if c C, nj
(7)
2.
> h
e(()))
if E y
(1,
ifc, n = =
7

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
Combining equation and equation we note that when at least node in edge is single-labeled, the label homophily of the corresponding edge will be equal to more than that in the static graph, thereby completing the first part of the proof.
Scenario 3: In the third scenario, where two multi-labeled nodes and are connected, at any time step t, when j(i,j) appears in the subgraph Gt, holds n D # 0 and C₁ n3i * In this scenario, the label homophily of an edge depends on the relationship between V n y and C.:
0 0= hog < hg
((..)
if n3 nc= =
(el(a)) = TAsK-IL SETTING
if no + #0,3 nuus na c ni c
2 21 CLASS-IL SETTING
Ng. ho(h))
lig
c(G))
if no CC C, S y nom
h ((d)))
1 2 ng (i.5)
Note that all the statements hold in both incremental settings except for the second condition, where V n noy C, is the strict subset of Y nov and C. With relatively smaller size of C₂l K 2 in our setting, we have the FlL SETTING, ()) n = 1 and D U = 2:
1o% n 2
h ((t.)) Gr
(9)
while in the CLASS-IL SETTING, because {}] n3%l 2 107 U32 - Kt, obtain
DI N DY 2 2t
ng.
(10)
We can now upper bound the probability the worst case event, i.e., when an edge e(t,j) exists at time t but Conynng nas 0. This can only happen if the classes in set C, are chosen from the set y U'U \J" nyv, For TASK-IL SETTING, the probability of choosing at least one element of C, from the common labels of node i and j is equal to ng (e(i.), Then the probability that none of the classes in C, appear in the common set at most (1 -1- -g--nhh (o()))) ) The proof is completed by noting the fact that |C,| K for TASK-IL SETTING and |Cr| Kt for CLASS-IL SETTING at time step t.
3.4 Comparison With Previous Evaluation Frameworks
In response to overlooked challenges in established CGL and MLCL evaluation frameworks, as detailed Section 1 our framework tackles these issues by the following.
Incorporation of the multi-label scenario. Contrary to previous evaluation frameworks AGALE accommodates single-label and multi-label node nodes in the following ways.
For single-label nodes, our framework expands upon previous methods during the task sequence's creation phase. introduces dynamics in label correlations by allowing random class ordering to generate the task sequence. This results in diverse subgraph sequences, mimicking the random emergence of new trends in the real world.
Regarding the multi-label scenario, as shown in Figure 5 our framework allows for update/change of label assignments for given node in the TASK-IL SETTING and expansion of the node's label set in the CLASs-IL SETTING.
Information preservation and prevention of data leakage
described Section 3.2 the data partitioning strategies of AGALE ensure that no nodes from the original multi-label static graph removed while creating the tasks. labgle- nodes appear once in the task
8

---

Published in Transactions on Machine Learning Research (J22e/2024)
sequence in both settings, while multi-labeled nodes surface with different labels in TASK-IL SETTING and CLASS-IL, SETTING. Specifically, they appear with non-overlapping subsets of their label set in TAsk-Il. SETTING, and as the class set expands, their entire label set is guaranteed to be seen by the model before the final time step in CLASS -IL SETTING.
Previous CGL evaluation frameworks split the nodes into train and evaluation sets within each class, not considering the situation where one node can belong to multiple classes in the task. Such strategy may lead to data leakage as one node can be assigned to training and testing sets for the same task. During lask training on a subgraph comprising various classes, our framework ensures no overlap among the training, validation, and test sets. Single-labeled nodes exclusively belong to one class, preventing their re-splitting after the initial allocation. For multi-label nodes that have been allocated
particular class (see lines 11 and 12 in Algorithm 2. we exclude them from the remaining nodes of other classes they belong to, eliminating any potential data leakage during training and evaluation within one subgraph.
In addition, we approach the continual learning setting by not allowing the inter-task edges. This deliberate choice means that, upon the arrival of new task, the model no longer retains access the data from the previous time steps.
Ensuring fair split across different classes and the whole graph. Due to the differences in the class size, a split from the whole graph will result in the bigger class dominating the splits, leaving the small class underrepresented in the splits. Moreover, the split within cach class may result in data leakage in one subgraph, as explained in the previous paragraph. To maintain a fair split despite differences in class sizes, our framework prioritizes splitting smaller classes initially. It subsequently removes already split nodes from larger class node sets. This approach guarantees an equitable split within each class and from within the whole subgraph, preventing larger classes from dominating the splits and ensuring adequate representation for smaller classes.
Application for graph/edge-leve CGL. AGALE can be directly applied for the graph classification task, each input data is an independent graph without interconnections. For the edge classification task, our framework can be applied by first transforming the original graph G into line graph (G)), where for each edge in G. we create node in LG); for every two edges in G that have a node in common, we make an edge between their corresponding nodes in L()).
4 Related Work
4.1 Continual Learning
Continual Learning (van de Ven & Tolias 2019 Hadsell ct al. 2020 Nguyen et al. 2018 Aljundi et al. 2019 Li & Hoiem
2016 Alljundi et al. 2017 Wang et al. 2202aa) a fundamental concept in machine learning, addresses the challenge of enabling models to learn from and adapt to evolving data streams over time. Continual learning has applications a wide range of domains, including computer vision, natural language processing, and reinforcement learning, making an active area of research with practical implications for the lifelong adaptation of machine learning models. Unlike traditional batch learning, where models are trained on static datasets, continual learning systems aim to learn from new data while preserving previously acquired knowledge sequentially. This paradigm is particularly relevant in real-world scenarios where data is non-stationary and models need to adapt to changing environments.
The key objectives continual learning are to avoid catastrophic forgetting, where models lose competence in previously learned tasks as they learn new ones, and to ensure that the model's performance on earlier tasks remains competitive. Various techniques have been proposed in the literature to tackle these challenges, which can be categorized into four categories.
Knowledge distillation methods. The methods from this category (Li & Hoiem 2016 Wang et al. 2021 2020b
retain the knowledge from the past by letting the new model mimic the old model on the previous task while adapting to the new task. Overall, the learning objective can be summarized as to minimize the following loss function:
C= NoLold (Yo, Y.) + Lnew (nn, Yn
+ R.
(11)
where Cold and Lnew represent the loss functions corresponding the old and new tasks, respectively. The parameter Xo is the weight for balancing the losses, and R encapsulates the regularization term. The process of

---

Published in Transactions on Machine Learning Research (J024/2024)
transferring knowledge from pre-existing model (teacher) to a continually evolving model (student) in knowledge distillation unfolds within Cola. where the new model undergoes training to align its predictions on new data for the old task, denoted as Y.. with the predictions of the previous model on the same new data for the old task, represented as Yo. Simultaneously, the new model approximates its prediction of the new data on the new task Y, to their true labels n,- For example, LwF (Li & Hoiem 2016) minimize the difference between the oulputs of the previous model and the new model on the new coming data for the previous tasks while minimizing the classification loss of the new model on the new task.
Regularization strategies. The methods in this category maintain the knowledge extracted from the previous task by penalizing the changes in the parameters 0 of the model trained for the old tasks. Typically, the following loss is minimized:
[()) = Lnew (0) + A Σ 24 (0: 02-") 0:-)
(12)
where Lnew denotes the loss function for the new task, 0 is the set of model parameters. The parameter À functions the weight governing the balance between the old and new tasks, while 92 represents the imporlance score assigned to the ith parameter 0j For example, MAS (Aljundi et al.) 2017] assigns importance scores for the parameters by measuring how sensitive the oulput is to the change of the parameters. The term 0, refers to the prior task's 's parameter determined through optimization for the previous task.
Replay mechanisms. Methods from this category extract representative data from the previous tasks and employ them along with the new coming data for training to overcome catastrophic forgetting (Shin et al. 2017 Kim et al.. 2020b). Methods under this category mainly differ with respect to their approaches to sampling representative data from the old task for storage in the buffer. For example, Kim et al. 2020b) maintains a target proportion of different classes in the memory to tackle the class imbalance in the multi- label data.
Dynamic architectures. Methods from this category (Lee et al.
2017 Wei et al. 2021 dynamically expand their architecture when needed for new tasks. This expansion may include adding new layers or neurons to accommodate new knowledge. For example, Lee et al. (2017) dynamically expands the network architecture based on the relevance between new and old tasks.
Another line of work in CL focuses on benchmarking evaluation methods. For instance, Farquhar & Gal 2019) and Lange et al. (2023) provide more robust and realistic evaluation metrics for the CL methods, incorporating real-world challenges like varying task complexities and the stability gap.
4.2 Continual Graph Learning
As a sub-field of continual learning, Continual Graph Learning (CGL) addresses the catastrophic forgetting problem as the model encounters new graph-structured data over time. Within CGL, two primary lines of work exist. The first. involves establishing evaluation frameworks that define incremental settings in CGL scenarios and their corresponding data partitioning algorithms. The second line of work focuses on proposing new methods based specific predefined CGL incremental settings derived from these evaluation frameworks. Our work mainly falls into the first category in which we develop a more holistic evaluation framework covering the multi-label scenario for graph- graph-structured data.
The previously established CGL frameworks focus on benchmarking tasks in CGL. For instance, Zhang et al. 2022 defined Task- and Class- Incremental settings for single-labeled node and graph classification tasks CGL and studied the impact of including the inter-task edges among the subgraph. Ko al. (2022) expanded this by adding the domain- and iime-incremental settings and including the link prediction task in the CGL benchmark. Additionally, surveys like Febrinanto et al. (2022) and Yuan et all (2023) focus on categorizing the approaches in CL and CGL.
However, none the above works sufficiently addressed the complexities of defining the multi-label node classification task within the CGL scenario. The only exception is Ko et al. (2022), which used graph with multi-labeled nodes, but that too in a domain incremental setting. In particular, each task was constituted of nodes appearing from a single domain. Consequently, a node appears in one and only one task together with all of its labels. This does not cover the general multi-label scenario in which the same node can appear in multiple tasks each time with different or expanding label sets.
10

---

Published in Transactions on Machine Learning Research (J224/2024)
Existing methods for CGL focus mainly the multi-class scenario and fall into one of the four categories (see the previous subsection) of continual learning methods. For example, GRAPHSAIL. (Xu et al. 2020) is knowledge distillation approach that distills each node's s local and global structure and its self-embedding knowledge, respectively. Regularization approach TWP (Liu et al. 2020 adds a penalization to the parameters that are important to the learned topological information in addition to the task-related loss to stabilize the parameters playing pivotal roles in the topological aggregation. ERGNN (Zhou & Cao 2021) based on the replay mechanism and carefully selects nodes from the old tasks to the buffer and replays them with the new graph. |aagg al. (2020a) combines replay and regularization to preserve existing patterns.
4.3 Learning on dynamic graphs
Since streaming graphs find applications in various domains, including social network analysis, recommendation systems, fraud detection, and knowledge graph refinement, several methods (Wang et al. 2023b Yu et al. 2018 2017
Xu et al. 2019) have been proposed in the field of dynamic graph learning (DGL) to utilize the knowledge from the past to enhance the model's performance on the graph in the current timestamp. For example, Rossi et al. (2020) uses the memory unit to represent the node's 's history in the compressed format, Pareja et al. (2019) uses recurrent architecture between the models trained for the adjacent time steps to let the new model inherent knowledge extracted from the old tasks. However, the designing goal the methods DGL is to utilize the knowledge extracted from the old tasks enhance the performance of the model on the current task, while in CGL, we focus on the catastrophic forgetting problem, iee, the model needs not only perform well on the current task but also on the previous tasks in the task sequence. We compare and analyze the models from these two categories in detail in Section 6
4.4 Application of graph machine learning in continual learning
Some work [Tang & Malteson 2021 Liu et al. 2023) also attempts use graph structures to alleviate catastrophic forgetting in Euclidean data. For instance, Tang & Matteson (2021) augments independent image data in memory with learnable random graph, capturing similarities among them to alleviate catastrophic forgetting. However, as
our current focus is solely on graph-structured data, these endeavors fall beyond the scope of this study.
5 Experiment Setup
In this section, we test the state-of-art models from CL, DGL, and CGL domains. Note that in this study, we employ P = 3, indicating that we generate three random orders for the classes in each dataset in the experimental section.
We introduce the models according to their categories.
5.1 Methods
This subsection introduces all the methods used in the experiment section. The CL methods use Graph Convolutional Network (GCN) (iipf & Welling 2016) as the backbone.
SIMPLEGCN: We train GCN on each of the subgraph sequences without any continual learning technique, which is denoted as SIMPLEGCN in the following sections.
JOINTTRAINGCN: We also include GCN trained on all the tasks simultaneously and therefore should not have the catastrophic forgetting problem. This setting is referred to as JOINTTRAINGNN in the following section.
Continual Learning Methods: We choose Learning Without Forgetting (LwF), Elastic Weight Consolidation (EWC), and Memory Aware Synapses (MAS) from this category. LwF distill the knowledge from the old model to the new model prevent the model from catastrophic forgetting. EWC and MAS are both regularization-bass methods. The difference is that EWC penalizes the changes in the parameters that important to the previous task, while MAS measures the importance of the parameters based on the sensitivity of the output on the parameters.
Dynamic Graph Neural Network: We choose EVoLVEGCN (Pareja et al. 2019 from this category, which uses recurrent architecture between the models trained for the adjacent time steps to let the new model inherent knowledge extracted from the old tasks enhance the model's performance the current task.
11

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
Continual Graph Learning Methods: We choose ERGNN [hou & Cao 2021) from this category, which samples representative nodes from the old tasks in the buffer and replays them with the new data to address the catastrophic forgetting problem.
5.2
Datasets
We demonstrate our evaluation framework on 3 multi-label datasets in this work. We also include multi-class dataset CORAFULL as an example demonstrate the generalization of our evaluation framework on single-label nodes. We include the description of the CORAPULL and the results on it in the Appendix A.2
The inter-task edges are defined in (Zhang et al. 2022) as the edges that connect the new subgraph to the overall graph. We do not allow inter-task edges in our evaluation framework, i.e., at each time step, only the subgraph for the new task is used as input. The reason is that in CL, the assumption is that the model loses access to the data from the previous time steps. With the inter-task edges, the node features from the previous time step would also be used as input, which violates this assumption and alleviates the forgetting problem. Below, we introduce the datasets used in this work:
1. PCG(Zhao al 2023 in which nodes are proteins and edges correspond to the protein functional interaction, and the labels the phenotype of the proteins.
2. DBLP(Akuuuobi et al. 2019), in which nodes represent authors and edges the co-authorship between the authors, and the labels indicate the research areas of the authors.
3. Yeip(Zeng et al. 2019, in which nodes correspond to the customer reviews and edges to their friendships with node labels representing the types of businesses.
The statistics about the datasets are summarized Table We use the label homophily defined for multi-label graphs in Zhao al. (2023). Following the application of data partitioning algorithm, the given static graphs by the datasets are split into subgraph sequences. We also summarize the characteristics of the subgraphs provide insights into the partitioned structure.
Table 1: The data statistics. Specifically, [V). J&). JC), [C] and Thomo denote the number of nodes, edges, classes, mean label count per node, and label homophily of the static graph given by the dataset, respectively. [T] signifies the count of tasks in the resulting task sequence. Additionally, [/ and |ε represent the average number of nodes and edges in a subgraph. Further details on label homophily are captured through Irlesk and [rldd. representing the averaged label homophily of subgraphs in the TASK- II. SETTING and CLASS II SETTING), respectively.
17
33
C
Thomo
1sk
|'
PCG
3K
37K
15
1.93
7
0.17
808
4763
0.64
0.38
DBLP
28K
68K
4
1.18
2
0.76
15K
37K
0.86
0.81
YELP
716K
7.34M
100
9.44
50
0.22
121K
921K
0.75
0.47
In Theorem ! we theoretically analyzed the label homophily the edges in the subgraphs where we showed that in cases of single-labeled nodes and for higher homophily edges, the homophily in subgraphs typically increases. Table further shows that the average label homophily of the subgraphs is in fact higher than the label homophily of the corresponding static graph.
5.3 Evaluation
5.3.1 Metrics
We evaluate the models using performance matrix M E R where M denotes the performance score reported by an evaluation metric (e.g. AUC-ROC, average precision etc.) on task Sy after the model has been trained over sequence of tasks from S S,. At each time step I, the average performance of the model is measured by the
12

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
average of the model's performances task S1 task St, ie., the average of the row i in performance matrix M. After the whole task sequence is presented to the model, we report the average performance AP as:
Σ Mr. AP
(13)
T
which the higher, the better.
We use the average forgetting AF score proposed in Lopez-Paz & Ranzato (2017). The forgetting task S; is measured by the performance change on task S; after the model is trained on the whole task sequence. Formally, we report the average forgetting AF on all the tasks as:
AF EL (Mr, M.))
(14)
T-1
Note that we here compute a single metric to quantify the incurred forgetting over past tasks when the model is trained for the last task Sy. The summand indicates the performance decrease on some task S after learning on later task ST.
When the average forgetting is negative, its absolute value indicates the averaged performance decrease on all previous tasks when the model is trained on the last task Sy in the task sequence.
A positive AF score indicates that the performance on some of the past tasks actually increased after training on task Sr. A positive AF score might the result of correlation among tasks that the model exploited, thus showing an improvement over past tasks.
Such observation may be when the tasks from graph are highly correlated with each other, training on the new task would help further improve the performance the old tasks.
Overall, we report the AP and AF for each model, and the scores we obtain from the two metrics are interpreted in the following Table
high AF
low AF
high AP
preserves well-rounded knowledge across all the tasks
performs well on the new task, while for- getting about the old tasks forgets about the old task, and fail to per-
low AP
preserves the knowledge from the old tasks and harms the overall performance indi- cates the tasks are not correlated, improve- ments on one task harm the performance on the other tasks
form well the new task
Table 2: The interpretation of the average performance score (AP) and the average forgetling score (AF).
5.3.2 Visualization
We use the heatmaps and lineplots to visualize the performance matrix M. Due to the limited space, we add the heatmaps in the Appendix[A.4 The lineplots are shown in Figure which have the time steps as æ axis, the y axis indicates the average performance of the model over all the tasks that have been encountered so far.
6 Results and Analysis
In this section, we summarize the experimental results on the multi-label datasets the TAsk-IL SETTING and CLASS-IL SETTING defined in section in the Table 3 and Table respectively. use a single numerical value to quantify the overall performance of the models, we calculate an average performance matrix M from the performance matrices from the three random splits and report the AP and AF from the averaged performance matrix.
13

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
Average Precision
0.6
40-
betler then- age worse-than-average
25
worse than-average
better than--han-aae average
percentage ot
30-
15
0.4
20
percentage
TaskiL subgraph
10
ClassilL subgraph
Joint train graph
Hamophily Level
D.4
0.6
0
10
1.0
number per
homophily in the direct neighborhood of node
(a) The visualization of the performances of GCN the subgraphs and the joint train graph from PCG and the label ho- mophily of the graphs.
(b) The distribution of the number of bels per node in the better-than-are thargae subset and in the worse-than than-aveeagee sub- set.
(c) The distribution the label homophily of the nodes in the hetter-than-averaa subset and in the worse-than sarse-than-aveen than-average sub-
Figure 6: Visualization of the analysis on the performance of SIMPLEGCN and JOINTTRAINGON using PCG example.
Lower and Upper Bounds in CGL
0.64
0.95
0.85
Simpletic
Burraaee Reformance
Avcrage Rerformance
Average Rerorrance
0.50
CWC
PAS
0.85
0.73
EvelveGCN
ERGNY
0.70
0.38
0.00
0.56
EWC
MNS
EvclwOON
0.73
0.0
0.2
0.9
1.0
10
20
20
50
Time Step
Time Steo
Time Step
(a) PCG
(b) DBLP
(c) YELP
In TASK-IL SETTING
0.50
feterage Perfomance
Average Peformnec
0.90
fveroge Derformnnce
EWCC
SimpletENN
RAS
0.50
0.03
Lxs
ExclowEIC
0.3
0.70
BHUNN
0.35
BM
0.30
0.0
0.2
04
0.5
1.0
19
30
lime Step
Time Step
lime
Step
(d) PCG
(e) DBLP
(f) YELP
In CLASS-IL SETTING
Figure 7: Learning curves showing the dynamics of the average performance during learning on the task sequences of different datasets. The color coding and legend names remain consistent across all subfigures. To avoid obstructing the line plot, we omit the legend the subplots corresponding PCG.
In the previous CGL frameworks [Zhang et al. 2022 Ko al. 2022), SIMPLEGCN and JOINTTRAINGCN are shown have the worst and the best performance. Such result also expected as SIMPLEGCN is employed sequential
14

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
data without any enhanced abilities to deal with catastrophic forgetting (thereby showing performance degradation) and (ii) in JOINTTRAINGCN all data is used to train the base GNN. However, the results from multi-label datasets in both incremental settings, as shown in Table 3 and Table | reveal that SIMPLEGCN and JOINTTRAIN are no longer suitable as lower and upper bounds for evaluating CGL performance in a more generalized scenario multi-label datasets. In the following, we theoretically and empirically analyze the rationale behind such finding.
6.1.1 Label homophily and GCN
GNNs, specifically GCN, which is used as base network are known to have better performance high label- homophilic graphs. As shown in Theorem | splitting labels into distinct prediction tasks and creating subgraphs for each task results in an increase in label homophily of the edges in the subgraphs as compared to that in the full graph. In particular, if in dataset there are large number of single-labeled nodes in the full graph with non-zero edge label homophily, the increase in label homophily of edges in subgraphs helps SIMPLEGCN to assign correct labels to the corresponding nodes. However, in JOINTTRAIN, the presence of diverse neighborhoods around single-labeled nodes leads to low label homophily, impacting its performance negatively.
Empirical evidence. Figure illlustrates the above statements with an example from one random shuffle of PCG using the subgraphs generated for the TAsK-IL SETTING (colored in blue), CLASS-IL SETTING (colored in green) and the original static graph given by the dataset (colored in red). On the x axis, we show the label homophily level of the input graphs, while on the y axis, we show the performance of SIMPLEGCN after it is trained on the subgraph in the corresponding incremental settings and JoINTTTAINNCC on the whole static graph. We make the following observations.
The subgraphs in TASk-IL SETTING and CLASS-IL SETTING have higher label homophily than the full graph, explaining the better performance of SIMPLEGCN as compared to JOINTTRAINGON.
We also observe that as compared to TASK-IL SETTING, the subgraphs generated for CLASS-IL SETTING have lower label homophily. This happens because of expanding label sets in CLASS-IL ILL SETTING.
In Figure 6b and 6c| we further analyze the causes of the bad performance of the JOINTTRAINGCN, We used the JOINTTRAINGCN model on test nodes from the joint train graph in PCG and calculated an average precision score for each node. The mean value of the scores is then used as threshold to divide the test nodes into the set of nodes that perform better-than-avvrage and the worse-than-averee bars in the plots. To remove the influence of the difference in the sizes of the subsets, we use the percentage of the nodes in the corresponding subset as the y axis.
performing node subset, indicated by the blue and orange
Based on the edge homophily defined in 1 we define the label homophily in the direct neighborhood of a node as the averaged edge homophily connected to this node:
Definition 2. For a node in the graph G, we define the label homophily of a node with respect to its immediate neighborhood N", represented as h², as the average of label homophily of the edges connected v:
h" Σ EeCMMEEE h6655)
W
We make the following observations.
In Figure 6b the percentage of single-labeled nodes in the thrse-than-average performing subset is higher than that the better-than-averag subset.
Figure 6c shows that in fact, the high percentage of worse-performing nodes have very low label homophily (computed using Definition 2 close to
The above two observations indicate that the performance of JOINTTRAINGCN suffers due to the presence higher percentage of low label homophily edges with at least one single-labeled node.
15

---

Published in Transactions on Machine Learning Research (J22e/2024)
For completeness, we include in 6c Kernel Density Estimation the node homophily distribution, which shows clear shift in the distributions of the label homophily in the better--erformin subset as compared to the worse-than-averas subset.
In the following sections, we summarize the performance of the chosen baselines in the TASK IL SETTING and CLASS-IL SETTING and provide a detailed analysis of the performances the baselines on different datasets.
6.2 Results in TASK-IL SETTING
Table 3: Performance of the baseline models in the TASK-IL SETTING setting. The performances are reported in Average Precision. "AP" stands for Average Precision, and the higher, the better. "AF" indicates the average forgetting, and the higher, the better.
TASK-IL
PCG
DBLP
YELP
AP
AF
AP
AF
AP
AF
SIMPLEGCN
54.34 + 0.04
-6.11 + 0.03
87.47 + 0.12
- -15.76
+ 0.00
54.87 + 0.03
- -1.43 + 0.05
LWF
58.12 + 0.05
-2.84
+ 0.02
95.01 + 0.01
-0.98 = 0.00
54.89 + 0.03
-2.07
0.05
EWC
56.17 +: 0.03
-3.77
+ 0.03
92.28 + 0.05
- -6.51 + 0.01
56.53 + 0.05
-0.17 + 0.02
MAS
56.26 + 0.04
22.64
+ 0.03
93.93 + 0.03
- 33.77 = 0.00
56.05 + 0.03
- 0..6 + 0.05
EVOLVEGCN
52.76 + 0.06
3.68
+ 0.03
78.94 + 0.25
35.20
+ 0.00
55.93 + 0.07
-5.11
+ 0.07
ERGNN
53.64 + 0.06
1.39
+ 0.02
67.70 + 0.03
24.96 + 0.00
54.99 + 0.03
-0 -0.92
+ 0.04
JOINTTRAIN
22.47 + 0.47
85.60 + 0.25
13.80 = 0.08
Table presents results for three real-world multi-label datasets in TASK-IL SETTING. In general, the knowledge distillation method LwF excels on graphs with shorter task sequences (e.g, PCG and DBLP with 7 and 2 tasks, respectively). In contrast, all methods perform comparably on the graph with a long lask sequence in YELP with 50 tasks, among which regularization-batt disparity arises because LwF distills knowledge only from the last time step, leading to a performance drop with longer sequences. Meanwhile, regularization-batt
methods like EWC and MAS slightly outperform other approaches. This
methods, like EWC and MAS, which penalize the changes the important parameters for previous tasks, prove effective for longer task sequences. The weak performance of the replay-based methods ERGNN indicates the importance of including the local topological structure around the nodes in the buffer instead of sampling isolated nodes in the buffer. Dynamic graph neural networks like EvoLvEGCN struggle with substantial forgetting despite achieving notable average precision scores because they only focus on the current task. We visualize the learning curve of the models in the TAsK-IL SETTING on PCG, DBLP, and YELP in Figure 7a 7b and 7c respectively. The x axis indicates the current time step, and the corresponding value on the y axis infers the average performance of the model at the current time step over all the tasks encountered so far.
6.3 Detailed analyses on different datasets
PCG. PCG has relatively shorter task sequence with 7 tasks. SIMPLEGCN showcases competitive scores but is susceptible to forgetting, indicating the low correlation among the tasks. LwF outperforms SIMPLEGCN and notably improved robustness against forgetting, which indicates the shorter task sequence in PCG contributes to the effectiveness of LwF in retaining task knowledge because LwF only distills knowledge from the previous model. EWC and MAS also exhibit competitive performance, demonstrating moderate resistance to forgetting. Meanwhile, because of the low correlations among the tasks, EVoLVEGCN faces challenges using with a lower performance and notable forgetting. JOINT TRAINGCN has the poorest performance because of the low label homophily level on the joint train graph.
DBLP. DBLP has the shortest task sequence length with only 2 tasks. LwF once again stands out with the highest performance and minimal forgetting. The SIMPLEGCN has the worst forgetting on DBLP compared to the other two datasets, indicating the tasks in DBLP have the lowest task correlation. While EWC and MAS present comparable performance to LwF, they suffer from worse forgetting. Notably, the low task correlation also results in the low performance and extreme forgetting of EvoLvEGCN and ERGNN, indicating the information from the previous task
16

---

Published in Transactions on Machine Learning Research (J22e/2024)
that lies in the model, and the data can not assist the model's performance on the new task. And because the joint train graph in DBLP has the highest level of label homophily, the JOINTRRIINGNN also achieves better performances compared to its performance on the other two multi-label datasets.
YELP. The YELP dataset is characterized by the longest task sequence encompassing 50 tasks and featuring the highest task correlations, which is indicated by the competitive performance shown by SIMPLEGCN, Despite the extended task sequence, training new task does not significantly impair performance the previous tasks. The long task sequence poses potential challenge for LwF, prolonged sequences lead to increased forgetting. EWC and MAS emerge as robust performers in this demanding setting, demonstrating solid performance with competitive performances and modest forgetting. EVoLVEGCN encounters a lower score coupled with considerable forgetting, as the high task correlation makes the utilization of the previous model helpful to improve the performance of the current task, EVOLVEGGN pays no attention to maintaining the performance on the old tasks. Additionally, ERGNN achieves a comparable performance with minimal forgetting, positioning JOINTTRAINGCN achieves the lowest performance because of the low label homophily level in the joint train graph.
strong contender on the YELP dataset.
6.4 CLASS-IL SETTING
Table 4: Performance of the baseline models in CLASS-II. SETTING setting. The performances are reported in Average Precision. "AP" stands for Average Precision and the higher the better. "AF" indicates the average forgetting, and the higher, the better.
CLASS-IL
PCG
DBLP
YELP
AP
AF
AP
AF
AP
AF
SIMPLEGCN
56.70 = 0.04
-2.48 = 0.03
93.22 = 0.03
-3.90 = 0.00
55.78 + 0.03
-1.56 + 0.05
LWF
38.13 + 0.13
3.48 + 0.03
81.98 + 0.18
-0.69 0.00
33.72 + 0.05
0.59 + 0.05
EWC
35.12 = 0.13
2.17 + 0.03
81.88 = 0.06
=.00
32.32 + 0.08
1.71 + 0.03
MAS
33.00 = 0.15
0.98 - 0.02
82.82 = 0.10
-4.87 0.00
32.07 + 0.07
0.04
EVOLVEGCN
29.44 - 0.12
0.23 + 0.01
68.18 + 0.03
29.69 + 0.00
23.45 + 0.06
-0.70 0.05
ERGNN
29.80 = 0.14
-2.82 - 0.03
59.99 = 0.12
3.14 + 0.00
24.00 + 0.06
-0.12
JOINTTRAIN
22.47 = 0.47
85.60 - 0.25
13.80 + 0.08
Table 4 presents results for three real-world multi-label datasets in CLASS-IL IL SETTING. Overall, SIMPLEGCN achieves a superior performance across all datasets. This performance contrast is noteworthy when compared to its performance on multi-class datasets the previous works (Zhang et al. 2022 Ko et al. 2022). The key distinction lies in our evaluation framework, where we enable the label vectors of multi-labeled nodes to expand during CLASS-IL SEtTING. In essence, this approach incorporates the previous labels of multi-labeled nodes part of the target labels in subsequent tasks. This strategy serves a dual purpose: it mitigates the problem of forgetting while simultaneously improving the performance on earlier tasks. This improvement is indicated by the positive average forgetting scores in the CLASS-IL SETTING context. The performance of JOINTTRAINGON is not influenced by the change in the setting, as it is trained on all the tasks simultaneously.
The drop in the performances of other baseline models is a result of the increasing number of classes in the tasks at each time step, i.e., the difficulty of the task increases at each time step. We visualize the learning curve of the models in the CLASS-IL SETTING PCG, DBLP, and YELP in Figure 7d 7 and respectively. The axis indicates the current time step, and the corresponding value on the y axis infers the average performance of the model at the current time step over all the tasks encountered so far. Below, we analyze the performance of the chosen baseline models on each of the datasets.
6.5 Detailed analyses on different datasets
PCG. SIMPLEGCN leads with the highest average performance overall tasks with low forgetting, as has no CL technique to prevent forgetting. On the other hand, the CL methods sacrificed the average performance on the task sequence but successfully maintained a positive AF. This means the knowledge distillation- and regularization-bant models are able to retain the knowledge from the old tasks in the CLASs-IL SETTING. EvoLvEGCN and ERGNN achieve
17

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
comparable average performance on the task sequence, but the ERGNN fails to retain the knowledge from the old task as it only samples the isolated nodes in the replay buffer while ignoring the topologiaa structure. JOINTTRAINGNN remains the worst-performing model because of the low label homophily in the input graph.
DBLP. DBLP has the shortest task sequence, but SIMPLEGCN and CL methods LwF, EWC, and MAS suffered from the most severe forgetting problem on it. These negative average forgetting scores observed in DBLP indicate low task correlation, ie., the knowledge from the old task hinders the model from achieving better performance on the new task. As the least multi-labeled graph, DBLP witnesses the least pronounced performance dip in the CLASS-IL SETTING compared to TAsK-IL SETTING. This observation suggests that multi-label datasets pose more challenging test for models when the label vectors of nodes continue to grow.
YELP. In YELP, nodes are more multi-labeled compared to PCG and DBLP, as shown in Table [ Overall, we see a clear performance difference in CLASS-IL SETTING compared to TASK-IL IL SETTING on YELP. Furthermore, knowledge distillation- and regularization-
methods surpass the dynamic graph neural network EvoLVEGCN and the replay- based method ERGNN. This is primarily due to the fact that EvoLvEGCN neglects the preservation of knowledge from previous tasks, which ultimately hampers overall performance. ERGNN, on the other hand, disregards the topological structure surrounding the sampled experience nodes, further impacting its efficacy in handling the evolving tasks.
7 Conclusion
We develop a new evaluation framework which we refer as AGALE for continual graph learning, Filling in the gaps in the current literature, we (i) define two generalized incremental settings for the more general multi-label node classification task, (ii) develop new data split algorithms for curating CGL datasets, and (iii) perform extensive experiments to evaluate and compare the performance of methods from continual learning, dynamic graph learning and continual graph learning. Through our theoretical and empirical analyses we show important differences of the multi-label case with respect to the more studied single-label scenario. We believe that our work will encourage the development of new methods tackling the general scenario of multi-label classification in continual graph learning.
Following the current literature, we focus on quantifying catastrophic forgetting in AGALE. In realistic scenarios, there is also the case where the model could be required to selectively forget about the past. For example, users in the social network might not further show interest in certain topics and un-follow some of the friends. Developing new evaluation metries as well as new models to reward selective forgetting of some tasks while avoiding catastrophic forgetting overall is an interesting avenue for future research.
References
Uchenna Akujuobi, Yufei Han, Qiannan Zhang, and Xiangliang Zhang. Collaborative graph walk for semi-superviied multi-label node classification. CoRR, abs/1990,,9976, 2019. URL http:///rww..org/bbb/////
09706
Rahaf Aljundi, Francesca Babiloni, Mohamed Elhoseiny, Mareus Rohrbach, and Tinne Tuytelaars. Memory aware synapses: Learning what (not) to forget. CoRR, abs/1711.09601,, 2017. URL 09601
Rahaf Aljundi, Klaas Kelchtermans, and Tinne Tuytelaars. Task-free continual learning. CoRR, abs/ 2018. 03596
URL wwt.http://arxiv.oo
Rahaf Aljundi, Klaas Kelchtermans, and Tinne Tuytelaars. Task-fre continual learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Sebastian Farquhar and Yarin Gal. Towards robust evaluations of continual learning, 2019.
Falih Gozi Febrinanto, Feng Xia, Kristen Moore, Chandra Thapa, and Charu Aggarwal. Graph lifelong learning: A survey, 2022.
Raia Hadsell, Dushyant Rao, Andrei Rusu, and Razvan Pascanu. Embracing change: Continual learning deep neural networks. Trends in cognitive sciences, 24(12):1028-1044 1040, 2020.
18

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
Chris Dongjoo Kim, Jinseo Jeong, and Gunhee Kim. Imbalanced continual learning with partitioning reservoir sampling. CoRR, abs/2009.03632, 2020a.
wwt.:/rrggabb//09.... 03632
Chris Dongjoo Kim, Jinseo Jeong, and Gunhee Kim. Imbalanced continual learning with partitioning reservoir sampling, 2020b.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. CoRR, abs/1609.02907, 2016.
http:/ii..rrr/bb//////// 02907
Jihoon Ko, Shinhwan Kang, and Kijung Shin. Begin: Extensive benchmark scenarios and an easy-to-use framework for graph continual learning. arXiv preprint 2xtv:2211.14566. 2022.
Matthias De Lange, Gido van de Ven, and Tinne Tuytelaars. Continual evaluation for lifelong learning: Identifying the stability gap, 2023.
Jeongtae Lee, Jachong Yoon, Eunho Yang, and Sung Ju Hwang. Lifelong learning with dynamically expandable networks. CoRR, abs/1708.01547, 2017. URL
01547
Zhizhong Li and Derek Hoiem. Learning without forgetting. CoRR, abs/1606.09282, 2016. URL httt::/tt/art org/ ht///bbs/16 166. 09282
Huihui Liu, Yiding Yang, and Xinchao Wang. Overcoming catastrophic forgetting in graph neural networks. CoRR, abs/2012.06002, 2020. URL httptttps///axiv.
wwtp/bg/////........//g httttss//arxiv.oor//b///211122
20000000022222 06002
Jinghua Liu, Yaojin Lin, Weiping Ding, Hongbo Zhang, and Jixiang Du Fuzzy mutual information-based multi-label feature selection with label dependency and streaming labels. IEEE Transactions on Fuzzy Systems, 31:1-15, 01 2022.
doi: 11. BALL:0//TUUZZ.222233884444
Jinghua Liu, Yaojin Lin, Weiping Ding, Hongbo Zhang, and Jixiang Du Fuzzy mutual information multilabel feature selection with label dependency and streaming labels. JEEE Transactions Fuzzy Systems, 31(1):77-91, 2023. doi: 10.110//TFU7Z222222..11444
David Papez-Paz and AurclA Ranzato. Gradient episodic memory for continuum learning. CoRR, abs//a06.08225 1706.08800, 2017. URL
http://vwwrrga/b////oaa/bssss/ 1706. 08840
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? CoRR, abs/2106.06134, 2021.
06134
Cuong V. Nguyen, Yingzhen Li, Thang D. Bui, and Richard E. Turner. Variational continual learning, 2018.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, and Charles E, Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. CoRR, abs/1902.10191, 2019. htl.itttp///xxxi.or///bbba
10191
German Ignacio Parisi, Ronald Kemker, Jose L. Part, Christopher Kanan, and Stefan Wermter. Continual lifelong learning with neural networks: A review. CoRR, abs//880.00756, 2018. URL
07569
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael M. Bronstein. Temporal graph networks for deep learning on dynamic graphs. CoRR, abs/2006.10633, 2020. URL https:
10637
Hanul Shin, Jung Kwon Lee, Jaehong Kim, and Jiwon Kim. Continual learning with deep generative replay. Advances in neural information processing systems, 30, 2017.
Binh Tang and David S. Matteson. Graph-based continual learning, 2021.
Gido M. van de Ven and Andreas S. Tolias. Three scenarios for continual learning. CoRR, abs/1904.00774, 2019. URL http://arxiv.
http://arxiv..rg/aas///oooo wwwp://w.or/bb/////eeee
19

---

Published in Transactions on Machine Learning Research (J22e/2024)
Gido M Van de Ven and Andreas S Tolias. Three scenarios for continual learning. arXiv preprint arXiv:1904.07734 2019.
Junshan Wang, Guojie Song, Yi Wu, and Liang Wang. Streaming graph neural networks via continual learning. CoRR, abs/2009.10951, 2020a. URL ttthtttss///xx arg/ 11920000..91111
Liyuan Wang, Xingxing Zhang, Hang Su, Jun Zhu. A comprehensive survey of continual learning: Theory, method and application, 2023a.
Tianchun Wang, Dongsheng Luo, Wei Cheng, Haifeng Chen, and Xiang Zhang. Dyexplainer: Explainable dynamic graph neural networks, 2023b.
Yigong Wang, Zhuoyi Wang, Yu Lin, Latifur Khan, and Dingcheng Li. Cifdm: Continual and interactive feature distillation for multi-label stream learning. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '21, pp. 2121-2124 New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450380379. doi: 10. 10.1145/3404835.446300
URL httph:t:////ee //toi.dooooo// org/10
1145/3404835 3463096
Zhen Wang, Liu Liu, and Dacheng Tao. Deep streaming label learning. In Hal Daumé III and Aarli Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 9963-9972. PMLR, 13-18 Jul 2020b. URL pottps://proceeding: mlr. mirrprees press/v119/ wang2On. html
Tong Wei, Jiang- Xin Shi, and Yu-Feng Li. Probabilistic label tree for streaming multi-label learning. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, KDD '21, pp. 1801-1811, New York, NY, USA, 2021 Association for Computing Machinery. ISBN 9781450383325. doi: 10. 10.1145/444554884477266 URL https://dde doi. org/ 10. 1145 04445/347448 3467226
Dongkuan Xu, Wei Cheng, Dongsheng Luo, Xiao Liu, and Xiang Zhang. Spatio-temporal attentive rnn for node classification in temporal attributed graphs. In Proceedings of the Twehty-Eighth International joint Conference on Artificial Intelligece, IJCAI-19, pp. 3947-3953, International Joint Conferences on Artificial Intelligence Organization, 2019, doi: 10.24966//jcai.2119555.4 URL http::ttt///ooo org/ 10. 1t1./110.444933 24963 aai.iiiaaaaa 2019/548
Yishi Xu, Yingxue Zhang, Wei Guo, Huifeng Guo, Ruiming Tang, and Mark Coates. Graphsail: Graph structure aware incremental learning for recommender systems. CoRR, abs/2008. 13517, 2020. URL https:////// org/ abs/2000 13517
Wenchao Yu, Wei Cheng, Charu C Aggarwal, Haifeng Chen, and Wei Wang. Link prediction with spatial and temporal consistency in dynamic networks. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pp. 3343-3349, 2017. 10. 114963/ijcat 2017/461
doi: 00.249633jjcai.2017/// URL
Wenchao Yu, Wei Cheng, Charu C. Aggarwal, Kai Zhang, Haifeng Chen, and Wei Wang. Netwalk: A flexible deep embedding approach for anomaly detection in dynamic networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '18, pp. 2672 2681, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450355520. doi: 10.1145/32198199322200 URL htttts
//doi org. 11 1445 0114/4//19888 32199999999911 /t////2999999.2202222222 3220024
Qiao Yuan, Sheng-Uei Guan, Pin Ni, Tianlun Luo, Ka Lok Man, Prudence Wong, and Victor Chang. Continual graph learning: A survey, 2023.
Hanqing Zeng, Hongkuan Zhou, Ajilesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. CoRR, //5//1977004999 2019. URL
1907. 04931
Xikun Zhang, Dongjin Song. and Dacheng Tao. Cglb: Benchmark tasks for continual graph learning. In Thirty-sixth Conference Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
20

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
Tianqi Zhao, Thi Ngan Dong. Alan Hanjalic, and Megha Khosla. Multi-label node classification graph-structured
data. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL /tt.ttttss//opeeeeviee net/
"orumm?d==Ehkv22jjD
Fan Zhou and Chengtai Cao. Overcoming catastrophic forgetting in graph neural networks with experience replay. Proceedings of the AAAI Conference on Artificial Intelligence,, 3565):47144472,, May 2021. doi: 10. 10.1/0//aai.. http://aaa.v35.16666000
URL
aaai. org/ index, http///AA//rtiill/////////ooo/
A Appendix
Organization. We analyze the characteristics of the subgraphs generated by AGALE and compare them with the full graph given in the dataset in Section A.1 Furthermore, we also apply our AGALE on single-label graph CORAFULL and summarize and analyze the results in section [A.2 to further demonstrate the generalization of AGALE in sing-label scenarios. Additionally, we provide detailed time and space complexity analysis Section A.3 and measure and summarize the run time of the conducted experiments as well. Last but least, we provide the visualization of the performance matrix using heatmaps in Section A.4
A.1 Data Analysis Of The Subgraphs
In this section, present analysis of the subgraphs derived by evaluation framework from the static graph in PCG, showcasing the efficacy of our approach. Figure illustrates the degree distribution of nodes within the seven subgraphs generated from the PCG dataset. We see from the degree distribution that the nodes in the subgraphs also have similar degree distribution to the nodes in the original static graph
Subgraph 1
Subgraph
Subgraph 3
Subgraph
100
60
Number of Node
Number Node
Number of Node
Number Node
60
40
40
20
20
20
0
0
100
20
40
20
40
60
100
Degree
Degree
Degree
Degree
Subgraph
Subgraph
Subgraph 7
125
Number of Node
Number of Node
150
Number of Node
150
75
100
50
50
20
40
50
100
150
200
100
200
Degree
Degree
Degree
Figure 8: The Node Degree Distribution In the seven Subgraphs Generated From PCG.
A.2 Application Of Our Evaluation Framework On Single-label Graphs
In this section, we provide an example of applying our evaluation framework to single-label graphs. Here, we use CORAFULL as an example. We summarize the characteristics of CORAFULL in Table As shown in the Table, CORAFULL has 70 classes, which are divided into 35 tasks in 3 random orders.
In Table 6 and 7 we summarize the performance of LwF and ERGNN on the dataset CORAFULl TASK II SETTING and CLASS-IL SETTING and use the line plots in Figure 9 visualize the learning curves of the chosen models in the two settings CORAPULI.
21

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
Table 5: The data statistics. Specifically, [V]. [&), [C], [4], and Thomo denote the number of nodes, edges, classes, mean label count per node, and label homophily of the static graph given by the dataset, respectively. [7') signifies the count of tasks in the resulting task sequence. Additionally, [ and [ε] represent the average number of nodes and edges in subgraph. Further details on label homophily are captured through Irlesk and Irles representing the averaged label homophily of subgraphs in the TASK- IL SETTING and CLASS- SETTIng), respectively.
V
[
[C|
T
Thomo
V 566
r tak
r eets
CORAFULL
19K
130K
70
35
0.57
1035
0.99
0.99
Table 6: Performance of the baseline models in TASK-IL SETTING setting. The performances reported in Average Precision. "AP" stands for Average Precision and the higher the better. "AF" indicates the average forgetting, and the higher, the better.
TASK- IL SETTING
CORAFULL
AP
AF
LwF
53.46 + 0.12
- -9.53 + 0.16
ERGNN
59.49 + 0.20
4.37 0.34
Table 7: Performance of the baseline models in CLASS-II, SETTING setting. The performances are reported in Average Precision. "AP" stands for Average Precision and the higher the better. "AF" indicates the average forgetting, and the higher, the better.
CLASS-IL SETTING
CORAFULL
AP
AF
LwF
5.42 + 0.15
-7.45 = 0.14
ERGNN
40.39 + 0.27
-56.08 + 0.25
A.3
Time And Space Complexity Analysis
Here, we provide theoretical time and space complexity analysis the models used in this work.
Complexity analysis for the base model. As the base model used by all compared methods is GCN (Kipf & Welling 2016), we first analyze its complexity. To keep the notations simpler let us assume that the feature (including the input features) dimension in all layers is equal to d. Let n, m denote the number of nodes and edges, respectively in the input graph at any time point. For the sake of brevity in the presentation, we assume that the number of nodes and edges stay the same for all time points.
For GCN, at each layer, the operation includes feature transformation, neighbourhood aggregation, and activation. The feature transformation over two layers leads to the multiplication of matrices of sizes (i) x d and d x d, and (ii) d x and x d which leads to a total time complexity of O(nd?).
And the neighborhood aggregation requires a multiplication between matrices of size n x n and n x d, yielding O(ndd). In practice, we compute this using a sparse operator, such as the PyTorch scatter function for each entry (i, in the adjacency matrix of the edge E, which yields total cost of O (md). Finally, the activation is element-wise function with the time complexity of O(n). Overall, the time complexity of L layer GCN is Onnd L + mdL nL).
For computing space requirements of GCN, we include (i) the space required for the input adjacency matrix of size n x n, (ii) the feature matrix of size n x d, and (iii) the model itself with d² + parameters for weight and bias in each layer. In total, the space complexity GCN is O(n² + nd + L(l + d)).
As all methods mentioned in this work either use GCN as the backbone model or are built upon GCN, we denote in the following discussion and the Table
8 the time and space requirement of GCN as TecN and SEON respectively.
22

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
Moan Puroormanc ERGNN In Task Selling On cona
Parforr Tuokll Sulking
2.0
Carci
0ved.
01-
Jawsage Teeeaee/etttrmme Peffumeraa
0020000 referarcs
02
0.
Timms Stop
(b) ERGNN in TASK- IL SETTING and CLASS- II SETTING on CORA- FULL
(4) LwTiin in SESTING CLASS-IL SETTING on CORAPOLL
Figure 9: Our Framework on Single-label Datasets
Complexity analysis of SIMPLEGCN. SIMPLEGCN trains a GCN for each time step & E T. And because it does not apply any continual learning techniques to remember from previous time sleps, the time is the same with GCN, ie., (((T)TGcN) and the space complexity is SCON-
Complexity analysis of LwF. LwF uses GCN as the backbone model, the GCN is trained at each time step L T for the new task, which gives the time complexity of O(TTTONN)) To do the knowledge distillation, the previous model also calls GCN forward passes with time complexity of O(T]TGoN) Overall, the time complexity is O(2 The space consumption consists of loading the current GCN model and the previous GCN model for the knowledge distillation, with space complexity of O(2SGCN).
Complexity analysis of EWC. EWC calls forward passes of GCN at each time step, and for each parameter at each time step / E 'T, the values on the diagonal of the fisher matrix are approximated using the value of each model parameter itself and its gradient. This is an element-wise calculation, which gives the time complexity of O(TT] x M), M indicates the number of parameters in the GCN, which is L(d + d). Overall, the time complexity of EWC is the time complexity of GCN plus the calculation of the fisher matrix, which O(T) x (TeeN + M)). The space requirement of EWC consists of the space requirement of GCN, and the matrix stores the gradients of the parameters at each time step of size O(T M). In total, the space complexity of EWC is O(SGON [T]M).
Complexity analysis of MAS. Similarly, MAS using GCN as backbone model, at each time step t E T, there are forward passes of GCN and the calculation of fisher matrix for parameters, which gives the overall time complexity of
+ M)). The space requirement MAS consists of the space complexity of GCN and one matrix for the gradient of the parameters of size O(M). which yields total O(SGON + M).
Complexity analysis of EVOLVEGCN. EVoLVEGCN is method from the category of Dynamic Graph Neural networks, which trains a new model at each time step with time complexity same as GCN, ie., TGON and updates the model parameter using a recurrent neural network using the corresponding parameter from previous time step as input, which has the time complexity of ( nd).. Overall, EVoLvEGCN is more expensive than the other Continual Learning methods with time complexity of (TGGN + In). The space requirement of EVoLVEGCN consists of the space requirement of the GCN plus the recurrent unit for the reset, update, and new gate with 3(d² + d). In our implementation, we O(2SeCN 3M).
recurrent layer for each layer in GCN. Thus the overall space complexity yields
Complexity analysis of ERGNN. ERGNN is a replay-based method. At each time step E T, it retrains the GCN on the current graph and the buffer-nodes-foor formed graph, and the sampling process goes through the nodes the new graph, which gives the time complexity of (2 + n). The space requirement ERGNN consists of the buffer size of [3] and the space complexity of GCN. In total, it yields the space complexity of OSSCCN + [B]).
23

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
Complexity analysis of JOINTTRAINGCN. JOINTTRAINGCN has the same time and space complexity the base model GCN. It uses the whole static graph input and is only trained once without the task sequence.
The above time and space complexity analyses are summarized in Table
Table 8: The simplified time complexity analysis. ToON and SEON corresponds to the time and space requirement of the base GCN model.
Model
Time Complexity
Space Complexity
SIMPLEGCN
O (CCN)
SGON
LWF
O (TCN)
((2SGCN)
EWC
O x (ToCN + M))
O (SGON (T
MAS
O (TGCN M))
O (SGON + +M)
EVOLVEGCN
(TGCN + +|[idd (ndd
022GCN + 3M)
ERGNN
0 (2 + +n)
(SGON [B])
JOINTTRAINGON
TCON
SGON
Besides, we also measured the run time of the experiments in this work. The results are summarized in Table Note that the running time of the experiments can be biased due different splits and how the resources distributed the computer. The theoretical analysis may provide more insights into the complexity of time.
Table The computation time of the experiments from Section second. The computation time is measured with one random split for each dataset.
TASK IL SETTING
CLASS-IL SETTING
PCG
DELP
YELP
PCG
DBLP
YELP
SIMPLEGCN
43.47
801.85
77163.32
88.31
886.79
104869.58
LWF
49.17
1193.40
142468.0 .01
111.23
732.76
264657.47
EWC
51.32
939.79
79804.48
135.44
790.73
200649.31
MAS
148.19
1169.50
75255.31
135.93
1230.88
145917.67
EVOLVEGCN
40.34
427 .99
120580.85
94.94
497.80
310540.41
ERGNN
47.27
536.20
416090.7 74
172.05
131.57
167624.39
JOINTTRAINGCN
166.82
796.19
80827.72
166.82
796.19
80827.72
A.4 Visualization of the Performance Matrix
In this section, we provide the visualization of the performance matrix using the heatmap on the three multi-label datasets. In the heatmap, each cell corresponds to unique entry in M, and its position in the heatmap mirrors its position in the matrix. We use the gradient the color to indicate the performance. The color intensity indicates the magnitude of the value.
In the Figure 10 11 and 12 we show the heatmaps correspond to the performance matrices of the baseline models in the TAsk-IL SETTING datasets PCG, DBLP, and YELP, respectively, while in the Figure 13 14 and 15 show the heatmaps correspond to the performance matrices of the bascline models in the CLASS-IL SETTING datascts PCG, DBLP, and YELP, respectively.
24

---

Published in Transactions on Machine Learning Research (Ju2e/2024)
942
CeI
GC
TOk+
Time
Time
Time
(a) Simple GCN
(b) LwF
(c) EWC
211
Time Step
Time Step
Time Step
(d) MAS
(c) EvolveGCN
(1) ERGNN
Figure 10: Visualization of the performance matrix of the methods in TaskIL setting on dataset PCG
Todla
Time
Time
(a) Simple GCN
(b) LwF
(c) EWC
Taaco
Time Step
Time Srpp
Time Stop
(d) MAS
(e) EvolveGCN
(f) ERGNN
Figure 11: Visualization the performance matrix of the methods in TaskIL setting on dataset DBLP
25

---

Published in Transactions on Machine Learning Research (lune/2024]
(a) Simple GCN
(b) LwF
(c) EWC
(d) MAS
(e) EvolveGCN
(f ERGNN
Figure 12: Visualization the performance matrix of the methods TaskIl. setting on dataset Yelp
9.0
34
341
(a) Simple GCN
(b) LwF
(c) EWC
D+1
Tude
(d) MAS
(e) EvolveGCN
(i ERGNN
Figure 13: Visualization of the performance matrix of the methods in CLASS-IL SETTING on dataset PCG
26

---

Published in Transactions on Machine Learning Research (June/2024]
340
Time Step
Time Stop
Time Stop
(a) Simple GCN
(b) LwF
(c) EWC
Thea
Time Step
Time Stop
Time Stop
(d) MAS
(c) EvolveGCN
(f) ERGNN
Figure 14: Visualization of the performance matrix the methods in CLASS-IL SETTING on dataset DBLP
(a) Simple GCN
(b) LwFF
(c) EWC
(d) MAS
(c) EvolveGCN
(f ERGNN
Figure 15: Visualization of the performance matrix of the methods in CLASS-IL SETTING on dataset Yelp
27


Reviews:
[{"review_id": "nChr90d5A4", "reviewer": "Reviewer_KrEX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The method is simple and easy to understand and follow. The intuition behind it is strong, and the problems it raises in the existing literature are important.\n- The empirical section is very methodological, checking a multitude of datasets and algorithms, suggesting new insights using AGALE\n- Although simplistic, the suggested method in the novel to the best of my knowledge\n\nWeaknesses:\n- The writing could be significantly more concise. Many points repeat themselves and are overly wordy. For example, the actual new ideas of the paper are introduced first on page 6, which is problematic. Section 2 contains many notations from previous art that are never used later on. Section 4 repeats many of the points made in Section 1 (specifically, 4.4 is very repetitive). Many subsections could have been shortened to just a few sentences. \n- The significance of the paper is marginal -- it suggests an evaluation for a very specific case: Graph data + continual learning + multi-label. While I understand that this can not be addressed by the authors, it is still a weakness of the work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper suggests new benchmarks for graph continual learning. The paper lists different continual graph settings and shows which of the current evaluation methods are more suited for which settings -- highlighting disentangles in all of them. Then, it offers a graph-aware evaluation framework. Afterward, the paper conducts an empirical study, comparing different algorithms on different datasets using the suggested evaluation method. The paper shows new insights gained on these datasets by using AGALE", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The major problem in my opinion is the writing. Once the paper is made more concise, I'm leaning toward acceptance, as its strengths outweigh its weaknesses.", "broader_impact_concerns": "Not applicable", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HtuloElYEh", "reviewer": "Reviewer_zeky", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths \n* This work tackles very important and challenging scenarios of graph continual learning where nodes in the graph can have multi-labels.\n* The proposed graph partitioning algorithms have advantages over previous ones, for validating the methods on graph continual learning settings.\n* The authors perform extensive experiments with multiple analyses, faithfully showing the efficacy of the proposed graph continual learning evaluation framework.\n* This paper is well-written and very easy to follow.\n\n\n### Weaknesses\n* The claim that the proposed graph partitioning algorithms can minimize the loss of the graph topological structure is not very convincing. While they can ensure fair splits across different classes, it does not ensure that the subgraphs after splits can maintain (or preserve) the original graph topology.\n* In the realistic scenario, some labels of certain nodes (e.g., users over the social network do not further show interest in certain topics and unfollow them) may be removed in the future, and considering (or at least discussing) this scenario along with the proposed evaluation framework would be worthwhile.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper points out the limitation of existing graph continual learning evaluation methods in that they focus mainly on single-label scenarios where each node has at most one associated label. To tackle this, the authors study more challenging and realistic scenarios where nodes in the graph can have multi-labels (with two different settings of task-incremental and class-incremental) and then propose simple yet effective graph partitioning algorithms to validate existing methods over those two continual learning settings. The authors perform extensive experiments and analyses with existing (graph) continual learning approaches, showcasing their advantages and limitations in the proposed challenging continual learning scenarios with multi-label nodes.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weaknesses above.", "broader_impact_concerns": "I don't see any concerns about the ethical implications of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5FoK3WHzQo", "reviewer": "Reviewer_p3Zp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n- The paper addresses the challenges of evaluating continual graph learning in both single-labeled and multi-labeled scenarios, filling gaps in the current literature.\n- The AGALE framework defines two generalized incremental settings for multi-label node classification tasks and develops new data split algorithms for curating CGL datasets.\n- The paper presents extensive experiments comparing methods from continual learning, dynamic graph learning, and continual graph learning, providing valuable insights into the performance of these methods in different scenarios.\n\n\nCons:\n- The paper does not provide a detailed comparison of the AGALE framework with other existing evaluation frameworks for continual graph learning. \n- The literature review is not sufficient in the literature review. For examples, some representative dynamic GNN is not included in the discussion of related works, such as:\nDyExplainer: Explainable Dynamic Graph Neural Networks. WSDM'24.\nNetWalk: A Flexible Deep Embedding Approach for Anomaly Detection in Dynamic Networks. KDD'18.\nLink Prediction with Spatial and Temporal Consistency in Dynamic Networks.  IJCAI'17.\nSpatio-Temporal Attentive RNN for Node Classification in Temporal Attributed Graphs. IJCAI'19.\n\n- The time complexity analyis is suggested to be included and the experiemnts on it are also good for the evaluation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces the AGALE framework, which aims to address the challenges of evaluating continual graph learning in both single-labeled and multi-labeled scenarios. It fills gaps in the current literature by defining two generalized incremental settings for multi-label node classification tasks and developing new data split algorithms for curating CGL datasets. The authors conducted extensive experiments to evaluate and compare the performance of methods from continual learning, dynamic graph learning, and continual graph learning.\n\nFurthermore, the paper presents performance comparisons of baseline models in the Task-IL setting, reporting Average Precision and average forgetting metrics. It also includes visual representations, such as the node degree distribution in subgraphs generated from the PCG dataset.\n\nIn conclusion, the AGALE framework contributes to the continual graph learning literature by providing a comprehensive evaluation framework that considers the challenges posed by multi-labeled scenarios. The paper's theoretical and empirical analyses shed light on the differences between single-label and multi-label cases, paving the way for the development of more effective models in continual graph learning.\n\nOverall, the paper offers valuable insights and important contributions to the field of continual graph learning, and its findings are likely to inspire further research in this domain.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Give a more thorough literature review.\n\n- give time complexity analyis", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper wants to improve and standardize evaluation of countinual graph learning. The paper lists different continual graph settings and offers a graph-aware evaluation framework. The reviewers were leaning positive but had some concerns about writing and related works. In the revised version post rebuttals most of these concerns were resolved making the paper ready for publication.
Decision: Accept (poster)