DyGRAIN: An Incremental Learning Framework for Dynamic Graphs

1 Introduction

Over the last few years, graph-structured data has been widely used in diverse domains, including social network analysis [Qiu et al., 2018], recommender systems [Berg et al., 2017], computer vision [Qi et al., 2017], and bioinformatics [De Cao and Kipf, 2018]. To deal with graph-structured data, various graph neural networks (GNNs) have been presented. GNNs learn powerful representations from nonEuclidean and high-dimensional graph information, resulting in state-of-the-art performance in many applications. While most of GNNs proposed so far assume that a given graph is static, many graph-structured data in the real world are dynamic graphs where nodes and edges vary over time as it evolves. A general approach for learning dynamic graphs is to retrain the full graph at every time step, requiring numerous amounts of cost. However, incremental learning is efficient and effective to learn representations of a dynamic graph. Recently, a few incremental learning methods for graph-structured data have emerged, but they investigate a static setting where aims to improve class learning (e.g., class-incremental setting) and focus to overcome only the catastrophic forgetting problem [Zhou and Cao, 2021; Liu et al., 2021]. Contrary to static graphs, incremental learning for dynamic graphs suffers from not only catastrophic forgetting but time-varying receptive fields of existing data. Since incremental inputs (e.g., nodes and edges) in dynamic graphs have dependencies with existing data that changes in receptive fields, learning a dynamic graph with an incremental approach should consider the influences propagated through dependencies with existing nodes. In the messagepassing mechanism, the receptive field of a node is determined with L-hop neighborhood nodes. If the node receives new nodes and edges in the neighborhood, its receptive field varies by new incoming influences propagated from the input through dependencies connected to. This is an important concern since time-varying receptive fields can cause a prediction change that may shift from correct labels to incorrect labels even with the same parameters. In addition, incremental learning has catastrophic forgetting problem that the learner model forgets the learned knowledge from the past while learning new information currently. Therefore, incremental learning for dynamic graphs confronts two important challenges which are time-varying receptive fields and catastrophic forgetting.

∗Corresponding Author

To address those challenges, we propose Dynamic Graph Incremental learning (DyGRAIN), a framework to train a dynamic graph, which captures the influential change in receptive fields over time and distills previously learned knowledge through the following components: (i) Influence Propagation identifies key existing nodes that are most influenced by new inputs in view of structure and feature. Our insight is that new dependencies can be captured by propagation from new inputs to existing data. Influence Propagation mitigates time-varying receptive fields. (ii) Knowledge Distillation with Truth(KDwTruth) selects existing nodes that are prone to forget previously learned knowledge by estimating loss discrepancy. It distills previously learned knowledge of selected nodes by leveraging ground truth labels. KDwTruth mitigates catastrophic forgetting. Our experiments show that our method outperforms state-of-the-art incremental learning techniques and graph incremental learning methods. Our framework is straightforward yet effective in capturing nodes influenced by new inputs and reducing catastrophic forgetting in a dynamic graph. Our contributions are as follows:

• We raise Time-varying receptive fields, a new problem occurring in dynamic graph incremental learning, where receptive fields of existing nodes vary due to dependencies with new inputs. This problem has a risk to the prediction shifting of existing nodes.
• We propose a novel and straightforward DyGRAIN that effectively captures crucial dependencies on a graph through both structure- and feature-based approaches and reduces catastrophic forgetting through more precise Knowledge Distillation of vulnerable nodes.
• We demonstrate that our method is effective to learn representations of dynamic graphs incrementally and experimentally verify on dynamic graphs processed from benchmark datasets including Open Graph Benchmark (OGB), where it consistently improves performance on both a given task and catastrophic forgetting.

2 RelatedWork

Incremental learning (i.e., continual learning or lifelong learning) aims to acquire increasing knowledge and extend it to future learning. However, incremental learning algorithms encounter catastrophic forgetting that the base learner model gradually loses the acquired knowledge when arriving data instances have different patterns or distribution shift from the previous time. Several studies on incremental learning overcoming catastrophic forgetting have been introduced.

Replay-based methods retrain sample data stored in memory [Chaudhry et al., 2019b] or pseudo-samples from the distribution of hidden representation [Shin et al., 2017] to relieve catastrophic forgetting. Alternatively, random sampling from a memory is utilized for estimating the gradient direction to constrain the optimization on new task from previous tasks [Chaudhry et al., 2019a]. These replay-based approaches show promising results on consistent fair scenarios. Another strategy to tackle catastrophic forgetting is an additional regularization term that consolidates previous parameters. There are regularization terms designed to distill the knowledge from a previous model to a current training model such as Learning Without Forgetting (LWF) [Li and Hoiem, 2017]. On the other hand, several regularization terms penalize important parameters that are estimated from a distribution over the model parameters. For example, Elastic Weight Consolidation (EWC) [Kirkpatrick et al., 2017] penalizes the parameter space to include important parameters from previous tasks. [Aljundi et al., 2018] proposes the regularization that can penalize parameters by estimating unsupervised importance, while [Zenke et al., 2017] estimates parameter importance in an online manner.

While conventional incremental learning methods for grid data are abundant, few approaches for incremental learning on graphs have been presented. GraphSAIL [Xu et al., 2020] proposed the online learning framework for dynamic user preferences, but it is limited to recommender systems and catastrophic forgetting. TWP [Liu et al., 2021] introduced the regularization-based incremental learning method that preserves important parameters from previous tasks and topological attention between adjacent nodes. ER-GNN [Zhou and Cao, 2021] proposed incremental graph learning using the replay approach. It selects nodes based on intra-class features, embedding distance, and influence function and retrains the selected nodes while learning a new task.

3 Methodology

The goal of our framework is to effectively learn incremental inputs of graph topology with dynamic nature. Since graphstructured data have dependency between data instances (i.e., nodes), incremental learning on dynamic graphs has major challenges: existing nodes influenced by new inputs (i.e., time-varying receptive fields) and catastrophic forgetting. To address these challenges, we propose an incremental learning framework for dynamic graphs, Dynamic Graph Incremental learning (DyGRAIN) which learns useful representations from pivotal nodes among existing nodes. In this section, we begin with the basic concepts of dynamic graphs and demonstrate the challenges of incremental learning on dynamic graphs, and then introduce the components of our framework DyGRAIN: Influence Propagation and KD with Truth.

3.1 Notation

Consider a dynamic graph G = {G(1) ,G(2) , · · · ,G(T)} that G(t) = (V (t) , E (t) ) denotes the graph at time step t. V (t) = {v1, v2, · · · , vN} represents a set of nodes interacted during a time step t and E (t) = {eij|vi, vj ∈ V (t) } represents a set of edges where nodes vi, vj ∈ V (t) are connected at a time step t. Both V (t) and E (t) change across time, and the cardinality in each time step may differ from the another. Likewise, A = {A(1) ,A(2) , · · · ,A(T) } denotes the adjacency matrices where A(t) ∈ RN (t)×N (t) is defined by A(t) ij = 1 if eij ∈ E (t) . X = {X(1) ,X(2) , · · · ,X(T) } represents a sequence of node features where X(t) ∈ RN (t)×F is defined as a set of feature vectors of each node x(t) i ∈ R1×F . As an input of graph neural networks, input data consist of an adjacency matrix and features, i.e., D(t) = (A(t) ,X(t) ).

Time-varying Receptive Fields

As new nodes and edges arrive incrementally on dynamic graphs, incremental learning (i.e., continual learning) that mainly trains new arriving inputs is essential to learn representations of dynamic graphs with efficiency. Unlike image domain or natural language domain, graph-structured data has a dependency with incremental inputs that leads to the unique challenge. Receptive fields of existing nodes can be changed when new nodes V (t) and edges E (t) appear because of the dependency. Specifically, V (t) influences the existing nodes that are connected in L-hop neighborhood where L is the number of layers in a GNN learner, changing the receptive fields of those existing nodes from the previous time step. We define this specific phenomenon as time-varying receptive fields and corresponding nodes as influence-receiving nodes.

3.2 Our Method

We propose DyGRAIN, a novel incremental learning framework for dynamic graphs that is designed to be aware of dependencies between new nodes and existing nodes while alleviating catastrophic forgetting. Specifically, our framework identifies the nodes most influenced new inputs, which we termed influence-receiving nodes, and vulnerable nodes that carry the previous knowledge but are prone to be forgotten. We employed the memory buffer Mwhich applies reservoir sampling [Vitter, 1985] for previous nodes and then trains the retrieved nodes from the memory buffer M for parameter update. Our framework retrieves nodes in two approaches to mitigate time-varying receptive fields and catastrophic forgetting.

Mitigating Time-varying Receptive Fields

To mitigate time-varying receptive fields, it should identify the existing nodes that are influenced by dependencies between new input D(t) . Thus, we propose Influence Propagation that is designed to measure the influence of the new input graph G(t) on the existing graph G(1:t-1) based on two perspectives: structure-based influence and feature-based influence. In other words, Influence Propagation is capable of estimating the extent of receptive field change upon a graph structure and a feature space. First, in the graph structurebased perspective, we assess the influence on the existing topology based on the distance from new inputs, i.e., how much new information propagates upon the graph structure. We first define Propagation matrix P and formulate V, a collection of the binarized values indicating whether node vi is in V (t) . V consists of nodes from the memory M and V (t) . Propagation matrix P is defined as

where A(t) ∈ RN (t)×N (t) is adjacency matrix at time step t, D ∈ RN (t)×N (t) is the degree matrix of A(t) and each node vi is from either V (t) or memory M. We obtain the matrix V(l) ∈ RN (t)+N (m)×N (t)+N (m) at the level of each l-th hop neighborhood when N (m) is the number of nodes fromM. V(l) indicate the amount of influence propagated at l-th hop neighborhood.

Then we define Structural Influence score πSI to measure influence propagated to each node. Given influence matrices V(1) , · · · ,V(L) according to the depth of a model L, Structural Influence score πSI is defined as

If πSI(vi) equals to 0, node vi is out of L-hop neighborhood of V (t) or an input node itself. We select the nodes based on K highest scores, i.e., Sstruct = arg topki πSI(vi) where k is determined by sample size B and score ratio r, i.e., k = B × r.

Secondly, in terms of node features X, our approach captures the influence of new input G(t) = (V (t) , E (t) ). Our method calculates how much the receptive field of existing nodes has changed compared to the previous time step. We use embedding vectors from a GNN learner since the receptive fields of nodes are projected into the embedding space. Thus, we estimate influence in feature space with the embedding vector of a node vj

where hθ indicates an output layer of arbitrary GNN learner model with L layers (i.e., fθ(x) = softmax(hθ(x))). hj represents the smoothed feature vector of vj ∈ N(i) which indicates neighborhood nodes up to L-hop of new input nodes ui ∈ V (t) . N(i) can be obtained from Structural Influence score πSI , i.e., πSI(vj) > 0. A(t) is the adjacency matrix of G(t) . To observe the amount of change in the receptive field of nodes over time, we define Feature Influence score πFI as

indicating a discrepancy of the receptive field by time, where h(t) j represents the embedding vector of a node vj at time step t. We choose nodes with K-highest deviation of the receptive field, i.e., Sfeat = arg topki πFI(vi). To learn the information of nodes influenced by a current input, we replay the nodes from the obtained subsets, i.e., SIP = Sstruct ∪Sfeat.

Then, a learner model trains the current input data D(t) with the retrieved node set SIP to consider dependency. That is, a subset of stored nodes is explicitly retrained, which can be called replay. Let YS be labels of nodes in subset S and C be the number of classes, then the objective function to mitigate time-varying receptive fields is defined as

Mitigating Catastrophic Forgetting

As widely known, incremental learning suffers from catastrophic forgetting problem that a learner model gradually forgets previously learned information while new knowledge is learned. The conventional incremental learning methods relieve catastrophic forgetting by adjusting stability-plasticity dilemma [Grossberg, 2012] through replay instances or consolidating parameter space. Graph-structured data can calibrate stability in a similar manner, however, it is neither feasible nor necessary to learn representations of the entire existing nodes. We define the method, Knowledge Distillation with Truth (KDwTruth), to identify informative but vulnerable nodes and distill its knowledge with a guarantee of correctness that further retains previous knowledge.

Identifying informative previous nodes that are vulnerable to new inputs, our approach starts with the matrix V(l) obtained from Eq.(3). Note that we discriminate the previous nodes that are out of l-hop neighborhood of new input nodes V (t) based on the structural relevance:

Given node samples VC and parameters from the previous time θ(t-1) , we can obtain loss values as

where ˜A(t-1) = A(t-1) + I is a normalized adjacency matrix. As a loss value implies which information should be stabilized, we select nodes from node samples VC by lower q percentile based on Eq.(9), i.e., V ′ = {vj ∼ VC|L(t-1) vj ≤ Pq(L(t-1) )}. To retrieve which candidate nodes in V ′ are prone to be interfered by A(t) on parameter space at current step t, the expected loss of V ′ is estimated as

As we aim to train nodes that provide learned knowledge but are prone to be interrupted, we estimate loss-based score πCF and randomly sample nodes as follows:

Score πCF equals to estimated deviation of loss per node vj from V ′ . We obtain the set of candidate nodes by random sampling from the selected k-highest deviation nodes. The set SKD contains nodes containing previously learned

Algorithm 1 Training Procedure of DyGRAIN

Required: At time step t > 1: Learner parameter θ(t-1) , New input D(t) , Memory buffer M, max epochs K Output: Parameter θ(t)

• 1: V←V (t) ∪ SAMPLE(M) by Eq.(1-3)
• 2: for k = 1 to K do
• 3: SIP ← Top-κ(πSI(vi ∈ V)) ⋃ Top-κ(πFI(vi ∈ V))
• 4: SKD ← SAMPLE(Top-κ(πCF (V ′ )) by Eq.(8-11)
• 5: L = ℓ(D(t) ; θ(t-1) )
• 6: LIP = ℓ(SIP ; θ(t-1) )
• 7: LKD = ℓ(SKD; θ(t-1) ) +γ · Σ∥Z (t) -Z (t-1) ∥22
• 8: θ(t) ← argminLTotal = L+LIP +LKD
• 9: end for
• 10: M ← Reservoir(M, D(t) )

information but are vulnerable to new inputs at time step t. DyGRAIN retains the previously learned information by Knowledge Distillation [Hinton et al., 2015]. In DyGRAIN framework, previous knowledge is distilled from the previous learner fθ(t-1) with hidden knowledge:

where C is the number of classes, � is the concatenation operator, c denotes the index for each class, τ is a temperature to soften probability, and γ is a hyperparameter.

Note that Knowledge Distillation cannot always guarantee hidden knowledge zi is correct under some certain conditions such as sudden distribution shift. However, DyGRAIN alleviates such incorrectness by leveraging ground truth labels. Besides, Eq.(14) can be approximated to minimizing Euclidean distance of a given logit from time t - 1 and t under mild assumption. Thus, the objective function mitigating catastrophic forgetting is defined as

Total Loss

Above all, the GNN learner trains input data D(t) . Then, the objective function is obtained as follows:

At time step t, our total objective function that mitigates timevarying receptive fields and catastrophic forgetting is defined as

Training procedure of our DyGRAIN is described in Algorithm 1.

4 Experiments

We evaluate our proposed method against a variety of stateof-the-art baselines on four node classification benchmark datasets. We verify our method on datasets simulated like the real world where a dynamic graph arrives in an incremental manner. In this section, we provide the experimental setting, quantative results, ablation studies, and analysis demonstrating the effectiveness of DyGRAIN.

4.1 Experimental Settings

Datasets. We evaluate the effectiveness of our DyGRAIN on the node classification task. We use Open Graph Benchmark (OGB) Arixv, Products [Hu et al., 2020], Reddit [Hamilton et al., 2017] and PubMed [Sen et al., 2008]. To simulate the dynamic scenario, we split the dataset into several incremental blocks. The graph is processed by time information if available. We assume the inductive setting on dynamic graphs [Xu et al., 2020]. Detailed statistics of each dataset are summarized in Appendix A.

Evaluation. We evaluate the performance in dynamic graph incremental learning with three metrics. Accuracy measures the performance on test data composed of nodes to be predicted and nodes predicted previously after learning the incremental block. Forgetting [Chaudhry et al., 2019b] measures the degree of catastrophic forgetting. We modify the Forgetting metric for dynamic graphs, observing the averaged rate of incorrect nodes used to be correct in the previous time.

Baselines To demonstrate the effectiveness of our method in dynamic graphs, we compare DyGRAIN with three wellknown incremental learning methods, two incremental learning methods for graph-structured data, fine-tuning which provides a lower bound, and retraining the full graph. We used three familiar incremental learning methods, Elastic Weight Consolidation (EWC) [Kirkpatrick et al., 2017] constraining parameter adaptation with the previous parameter space, Learning without Forgetting (LWF) [Li and Hoiem, 2017] that utilizes the previous model output as soft labels for previous tasks, and Experience Replay (ER) [Rolnick et al., 2019], directly retraining randomly sampled instances stored in the memory buffer. For graph-specified incremental learning, we used ER-GNN [Zhou and Cao, 2021] and Topological Weight Preserving (TWP) [Liu et al., 2021]. Furthermore, we compare our method using four GNN-based models, GCN [Kipf and Welling, 2017], GAT [Veliˇckovi´c et al., 2018], APPNP [Klicpera et al., 2019], and GCN2 [Ming Chen et al., 2020] as a base learner model. Implementation details are described in Appendix B.

4.2 Node Classification Task

Table 1 reports the results on incremental dynamic graph datasets created with official graph benchmarks. First, in terms of accuracy, we can observe our DyGRAIN consistently outperforming state-of-the-art incremental learning algorithms and graph incremental learning methods regardless of base learners. Especially, our method provides a significant improvement on OGB-Arxiv and OGB-Products. DyGRAIN shows 13.81% and 5.36% relative improvement in accuracy on OGB-Arxiv, compared to the lowest baseline and the second-best baseline, respectively. Even more, our method achieves a large relative improvement 7% in accuracy on OGB-Products compared to the second-best method, ER. Besides, DyGRAIN shows less than 1% discrepancy on retraining the full graph on most datasets, which indicates our proposed framework DyGRAIN is able to identify useful influence-receiving nodes which affected by incoming influence and properly reflect these nodes on learning incremental inputs. Also, our framework reaches the best or second-best performance in Forgetting evaluation. On the other hand, our DyGRAIN consistently shows state-of-the-art performance in both accuracy and Forgetting evaluation. This implies that addressing other problems (e.g., time-varying receptive fields) beyond catastrophic forgetting plays a key role in incremental learning on dynamic graphs. We further investigate the effectiveness of addressing time-varying receptive fields in the next section.

4.3 Analysis on Learning Influence-receiving Nodes

DyGRAIN is capable of learning existing nodes that have time-varying receptive fields which are critical in dynamic graph incremental learning. To demonstrate the ability to capture the time-varying receptive fields, we evaluate the performance of methods on the entire influence-receiving nodes at each time step. Figure 2 shows accuracy on influencereceiving nodes at each incremental block t. As shown in Figure 2, our method achieves the best performance at every incremental block on both OGB-Arxiv and OGB-Products. Besides, our method shows a smaller variance between incremental blocks compared to other baselines. In OGB-Arxiv dataset, we can notice that our method produces the best results with a less discrepancy between the accuracy of each incremental block. This implies that our method has the ability to capture the most influence-receiving nodes among the existing nodes.

4.4 Ablation Study

In this section, we empirically validate the efficacy of each component in DyGRAIN through ablation experiments. We evaluate average accuracy and average Forgetting with our framework without each component. To validate the efficacy of Knowledge Distillation with Truth, we split the component into Knowledge Distillation (KD) and ground truth label (GL). According to Table 2, our method constantly achieves better performances across all datasets. However, our method without each component (i.e., w/o IP, w/o KD, w/o GL) shows degraded results for accuracy, demonstrating the effectiveness of each component. Specifically, our method (w/o IP) shows the most decreased accuracy score. This implies the time-varying receptive fields, namely, influence-receiving nodes are pivotal in incremental learning for dynamic graphs. Moreover, we can see that our method (w/o KD) and our method (w/o GL) reduce the accuracy but increase Forgetting. As seen in Table 2, Forgetting has clearly increased without Knowledge Distillation and Ground truth labels. This verifies both components contribute to preventing catastrophic forgetting.

5 Conclusion

In this paper, we specified the genuine problem of incremental learning for dynamic graphs that existing nodes influenced by new incremental inputs. Its receptive fields are changing over time, which we named time-varying receptive fields. To address time-varying receptive fields and catastrophic forgetting, we propose DyGRAIN, a novel incremental learning framework for dynamic graphs. Our framework shows promising results on task performance, in terms of capturing new incoming influences on existing nodes and mitigating catastrophic forgetting. In the future, we would further improve DyGRAIN to handle unlabelled data and other graphrelated tasks (e.g., link prediction and graph classification).

Acknowledgements

This work was funded by National Research Foundation of Korea (NRF-2020R1A2C3010638), Ministry of Health Welfare, Republic of Korea (HR20C0021), and ICT Creative Consilience program(IITP-2021-0-01819).