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