  Continual learning seeks to empower models to progressively acquire
information from a sequence of tasks. This approach is crucial for many
real-world systems, which are dynamic and evolve over time. Recent research has
witnessed a surge in the exploration of Graph Neural Networks (GNN) in
Node-wise Graph Continual Learning (NGCL), a practical yet challenging paradigm
involving the continual training of a GNN on node-related tasks. Despite recent
advancements in continual learning strategies for GNNs in NGCL, a thorough
theoretical understanding, especially regarding its learnability, is lacking.
Learnability concerns the existence of a learning algorithm that can produce a
good candidate model from the hypothesis/weight space, which is crucial for
model selection in NGCL development. This paper introduces the first
theoretical exploration of the learnability of GNN in NGCL, revealing that
learnability is heavily influenced by structural shifts due to the
interconnected nature of graph data. Specifically, GNNs may not be viable for
NGCL under significant structural changes, emphasizing the need to manage
structural shifts. To mitigate the impact of structural shifts, we propose a
novel experience replay method termed Structure-Evolution-Aware Experience
Replay (SEA-ER). SEA-ER features an innovative experience selection strategy
that capitalizes on the topological awareness of GNNs, alongside a unique
replay strategy that employs structural alignment to effectively counter
catastrophic forgetting and diminish the impact of structural shifts on GNNs in
NGCL. Our extensive experiments validate our theoretical insights and the
effectiveness of SEA-ER.
