Streaming Graph Neural Networks via Continual Learning

Junshan Wang; Guojie Song; Yi Wu; Liang Wang

Source-linked AI summary

Streaming Graph Neural Networks via Continual Learning

Junshan Wang, Guojie Song, Yi Wu, Liang Wang

arXiv:2009.10951v2Sep 23, 2020cs.LGcs.SIstat.ML

TL;DR

Streaming graph distributions shift, so GNNs must learn new neighborhood patterns without forgetting historical knowledge. The paper proposes continual-learning-based streaming GNNs that detect new patterns and consolidate existing ones through replay and regularization, achieving comparable results to retraining while updating more efficiently.

Problem
Streaming GNNs must learn new patterns as graph distributions shift while avoiding catastrophic forgetting of historical patterns.
Method
The model detects affected nodes through approximate propagation-based pattern detection and consolidates existing knowledge using hierarchy-importance replay plus Fisher-information-based weighted regularization.
Results
Experiments on real-world and synthetic networks show that the model is more efficient than retraining while achieving comparable results and alleviating catastrophic forgetting.
Takeaways & Limitations
The framework provides incremental streaming-GNN updates that jointly capture new patterns and preserve existing knowledge.
Takeaways & Limitations
The posterior over GNN parameters is intractable, so the method adopts a Laplace approximation and Gaussian posterior assumption.

Abstract

from arXiv · show

Graph neural networks (GNNs) have achieved strong performance in various applications. In the real world, network data is usually formed in a streaming fashion. The distributions of patterns that refer to neighborhood information of nodes may shift over time. The GNN model needs to learn the new patterns that cannot yet be captured. But learning incrementally leads to the catastrophic forgetting problem that historical knowledge is overwritten by newly learned knowledge. Therefore, it is important to train GNN model to learn new patterns and maintain existing patterns simultaneously, which few works focus on. In this paper, we propose a streaming GNN model based on continual learning so that the model is trained incrementally and up-to-date node representations can be obtained at each time step. Firstly, we design an approximation algorithm to detect new coming patterns efficiently based on information propagation. Secondly, we combine two perspectives of data replaying and model regularization for existing pattern consolidation. Specially, a hierarchy-importance sampling strategy for nodes is designed and a weighted regularization term for GNN parameters is derived, achieving greater stability and generalization of knowledge consolidation. Our model is evaluated on real and synthetic data sets and compared with multiple baselines. The results of node classification prove that our model can efficiently update model parameters and achieve comparable performance to model retraining. In addition, we also conduct a case study on the synthetic data, and carry out some specific analysis for each part of our model, illustrating its ability to learn new knowledge and maintain existing knowledge from different perspectives.

1 INTRODUCTION

Streaming networks evolve and shift pattern distributions, requiring GNNs to learn new patterns while preserving historical knowledge. The proposed continual-learning framework incrementally updates representations and combines efficient pattern detection with replay and regularization, achieving comparable performance to retraining.

Streaming GNNs must learn newly emerging neighborhood patterns without overwriting existing patterns through catastrophic forgetting.
Continual learning is adopted to capture current-network patterns while consolidating knowledge from previous networks without storing and retraining all data.
The method detects new patterns approximately and preserves existing knowledge through hierarchy-importance node sampling and Fisher-information-based weighted parameter regularization.
Experiments on real-world and synthetic graphs show lower accuracy loss than other incremental models, comparable performance to retraining, and alleviated catastrophic forgetting.
The framework incrementally updates GNN parameters and node representations as streaming networks evolve and their distributions shift.

2 RELATED WORK

Prior network-embedding and dynamic-network methods largely target static graphs, temporal modeling, or efficient updates under settings that do not fully handle streaming graph structures. Continual-learning methods offer relevant regularization and replay ideas, but existing online approaches are not designed for complex networks.

Traditional SkipGram and GNN embedding methods are primarily designed for static networks, while SkipGram models are limited to transductive settings.
Dynamic-network models capture temporal information but often require training a new model at every time step, creating high computational complexity.
Continual-learning research includes regularization, replay, and parameter-isolation methods for consolidating knowledge from previous tasks.
Task-based continual-learning methods rely on task boundaries, whereas streaming scenarios often lack such boundaries.
Existing online continual-learning methods for independent data such as images do not handle streaming data with complex network structures.

3 PRELIMINARIES

The preliminaries define GNN representations, streaming graph evolution, and the limitations of simple update schemes. Streaming GNNs must update representations when graph patterns change, while avoiding both stale knowledge and catastrophic forgetting.

GNNs generate node representations by aggregating neighborhood information, and these representations support supervised node classification through cross-entropy loss.
A streaming network evolves as G_t = G_t−1 + ΔG_t, where each snapshot contains changing node attributes and network structures, including newly added nodes.
Streaming GNNs learn time-specific parameters that should produce satisfactory node representations for any node present at that time.
Network changes can create new patterns beyond the previous GNN, and affected nodes may extend beyond the directly changed nodes because graph information is interdependent.
Using a pretrained GNN can miss changed patterns, retraining the whole graph is costly, and online learning can cause catastrophic forgetting.

4 STREAMING GNNS VIA CONTINUAL LEARNING

ContinualGNN incrementally learns new patterns in evolving networks while consolidating existing knowledge. It detects affected nodes through information propagation and combines data replay with model regularization for preservation.

4.1 Model Framework: ContinualGNN learns new patterns and consolidates existing patterns simultaneously in streaming networks.Its objective separates loss on influenced network parts from consolidation of previous network data.
4.2 Detection for New Patterns: New-pattern detection scores nodes by representation changes between adjacent snapshots and selects influenced nodes above a threshold.The scoring function identifies nodes whose representations are substantially affected by network changes.
4.2 Detection for New Patterns: The approximation algorithm estimates influence through information propagation, reducing complexity from O(|V| × ˜m) to O(|ΔV| × ˜m + |N_L(ΔV)|).It uses propagation over affected nodes and their L-hop neighborhoods rather than traversing the entire network.
4.3 Existing Pattern Consolidation: Historical knowledge is consolidated through replaying a selected memory of nodes and applying weighted regularization to GNN parameters.Hierarchy-importance sampling improves replay selection, while regularization is derived from an approximated posterior and Fisher Information.
4.3.2 Model-view: The model-view method estimates the Fisher Information matrix from memory nodes and their neighbors because full-network computation is costly.The posterior is approximated as a Gaussian centered at the previous parameters, with covariance related to the Fisher Information matrix.

5 EXPERIMENTS

The experiments evaluate incremental node classification, catastrophic forgetting, and individual model components. They use four datasets and include a synthetic-data case study.

5 EXPERIMENTS: Experiments evaluate incremental node classification on four datasets to assess streaming-network learning.The evaluation focuses on whether the model can implement incremental learning efficiently.
5 EXPERIMENTS: A synthetic-data case study examines catastrophic forgetting, followed by detailed analysis of each model component.The study also analyzes the contribution of individual parts of the model.

5.1 Experimental Setup

The experiments evaluate ContinualGNN against eight baselines on three real-world and one synthetic dataset, using standardized deep-model settings and reported node-classification metrics.

Datasets: Experiments use three real-world datasets and one synthetic dynamic network with changing label distributions across 14 snapshots.The datasets include Cora, Elliptic, DBLP, and Synthetic.
Baselines: ContinualGNN is compared with eight baselines spanning SkipGram models, retrained GNNs, incremental GNNs, and continual learning.GraphSAGE retrained on the entire network is treated as an upper bound.
Implementation: All models use embedding size 64, while deep models use two 64-dimensional hidden layers with mean aggregation over 10 sampled neighbors.LINE and DNE concatenate first- and second-order proximity representations.
Evaluation Metrics: The evaluation reports averaged F1, accuracy, and running time per epoch for node classification, alongside accuracy on consecutive snapshots.Table 1 summarizes the averaged metrics, while Figure 1 tracks accuracy over time.
Implementation: ContinualGNN uses dataset-specific λ and m settings, with a detection threshold δ based on the ratio of influenced nodes among potential nodes.The threshold ratio is set to 0.8 for all four datasets.

5.2 Experimental Results

ContinualGNN achieves strong node-classification performance while learning new patterns and consolidating existing knowledge in streaming networks. Experiments show benefits in accuracy, efficiency, pattern detection, consolidation, and scalability.

Node Classification: ContinualGNN achieves the best performance among incremental models and results closest to the RetrainedGNN upper bound.Table 1 reports averaged F1 and accuracy across four datasets.
Node Classification: ContinualGNN maintains more stable accuracy over time than approaches that fail to learn new knowledge or preserve historical knowledge.On Synthetic, its performance recovers after short-term deterioration despite dramatic network changes.
Scalability: ContinualGNN scales more favorably than retraining as network size increases and trains about five times faster than retrained GNNs.The model remains convergent in a short time as streaming-data size varies.
Case Study on Synthetic Data: ContinualGNN preserves classification accuracy and separable representations when synthetic network structure or node-attribute distributions change.The case study evaluates nodes arriving at t0 and t8 across subsequent time steps.
New Pattern Detection: Approximation matches Naive and BFS in accuracy while requiring less detection time by calculating influence for fewer nodes.On Synthetic, Approximation and BFS have similar detection time because changed and influenced nodes are similar in number.
Existing Pattern Consolidation: Step-wise sampling improves results with little runtime difference, while weighted regularization outperforms L2 regularization and no constraint.The selected memory size is 250, and the best regularization weight on Synthetic is λ=200.
Existing Pattern Consolidation: Combining data-view and model-view preservation achieves better results than either perspective alone.The two perspectives compensate for each other’s deficiencies in node classification.

6 CONCLUSION

The paper addresses incremental GNN learning under distribution shifts by detecting new patterns and consolidating existing knowledge. Experiments show greater efficiency than retraining with comparable results.

6 CONCLUSION: The proposed model detects new patterns through traversal-based approximation and consolidates existing knowledge using historical data and the previous model.These mechanisms address incremental GNN learning when data distributions shift and new patterns appear.
6 CONCLUSION: Experiments on real-world and synthetic networks show that the model is more efficient than retraining while achieving comparable results.