  Despite significant advances in graph representation learning, little
attention has been paid to the more practical continual learning scenario in
which new categories of nodes (e.g., new research areas in citation networks,
or new types of products in co-purchasing networks) and their associated edges
are continuously emerging, causing catastrophic forgetting on previous
categories. Existing methods either ignore the rich topological information or
sacrifice plasticity for stability. To this end, we present Hierarchical
Prototype Networks (HPNs) which extract different levels of abstract knowledge
in the form of prototypes to represent the continuously expanded graphs.
Specifically, we first leverage a set of Atomic Feature Extractors (AFEs) to
encode both the elemental attribute information and the topological structure
of the target node. Next, we develop HPNs to adaptively select relevant AFEs
and represent each node with three levels of prototypes. In this way, whenever
a new category of nodes is given, only the relevant AFEs and prototypes at each
level will be activated and refined, while others remain uninterrupted to
maintain the performance over existing nodes. Theoretically, we first
demonstrate that the memory consumption of HPNs is bounded regardless of how
many tasks are encountered. Then, we prove that under mild constraints,
learning new tasks will not alter the prototypes matched to previous data,
thereby eliminating the forgetting problem. The theoretical results are
supported by experiments on five datasets, showing that HPNs not only
outperform state-of-the-art baseline techniques but also consume relatively
less memory.
