Hierarchical Prototype Network for Continual Graph Representation Learning
Authors: Xikun ZHANG
Dongjin Song
Dacheng Tao
Venue: NeurIPS 2021 Submitted (2021)

Abstract: Despite significant advances in graph representation learning, little attention has been paid to graph data 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. The key challenge is to incorporate the feature and topological information of new nodes in a continuous and effective manner such that performance over existing nodes is uninterrupted. To this end, we present Hierarchical Prototype Networks (HPNs) which can adaptively extract different levels of abstract knowledge in the form of prototypes to represent continually expanded graphs. Specifically, we first leverage a set of Atomic Feature Extractors (AFEs) to generate basic features which can
encode both the elemental attribute information and the topological structure of the target node. Next, we develop HPNs by adaptively selecting relevant AFEs and represent each node with three-levels of prototypes, i.e., atomic-level, node-level, and class-level. 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. Finally, we provide the theoretical analysis on memory consumption bound and the continual learning capability of HPNs. Extensive empirical studies on eight different public datasets justify that HPNs are memory efficient and can achieve state-of-the-art performance on different continual graph representation learning tasks.

Hierarchical Prototype Networks for Continual Graph Representation Learning
Anonymous Author(s)
Affiliation Address
email
Abstract
Despite significant advances in graph representation learning, little attention has been paid to graph data 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. The key challenge is to incorporate the feature and topological information new nodes in a continuous and effective manner such that performance over existing nodes is uninterrupted. To this end, we present Hierarchical Prototype Networks (HPNs) which can adaptively extract different levels of abstract knowledge in the form of prototypes to represent continually expanded graphs. Specifically, we first leverage a set of Atomic Feature Extractors (AFEs) to generate basic features which can encode both the elemental attribute information and the topological structure the target node. Next, we develop HPNs by adaptively selecting relevant AFEs and represent each node with three-levels of prototypes, i.e., atomic-level, node-level, and class-level. In this way, whenever new category of nodes is given, only the relevant AFEs and prototypes at each level will be activated and refined, while others remain uninterrupted. Finally, we provide the theoretical analysis memory consumption bound and the continual learning capability of HPNs. Extensive empirical studies eight different public datasets justify that HPNs are memory efficient and achieve state-of-the-a performance on different continual graph representation learning tasks.
5
11
13
15
17
18
19
20
Introduction
21
22
Graph representation learning aims to pursue a meaningful vector representation of each node so as to facilitate downstream applications such node classification, link prediction, etc. Traditional methods are developed based on graph statistics [23] or hand-crafted features [3] [6]. Recently, great amount of attention has been paid to graph neural networks (GNNs), such graph con- volutional network (GCNs) [2], GraphS AGE [10], Graph Attention Networks (GATs) [31] and their extensions 34 41 14
24
26
38). This is because they can jointly consider the feature and topological information of each node. Most of these approaches, however, focus on static graphs and cannot generalize to the case when new categories of nodes are emerging.
24
28
29
In many real world applications, different categories of nodes and their associated edges (in the form of subgraphs) are often continuously emerging in existing graphs. For instance, a citation network [27 32 20), papers describing new research areas will gradually appear in the citation graph; in updated to the graph. Given these facts, how incorporate the feature and topological information of new nodes
31
33 co- co-purchasing network such as Amazon 4 new types products will continuously
35 in continuous and effective manner such that performance over existing nodes is uninterrupted is a critical problem to investigate.
37 To address this issue, various types of continual learning approaches can be considered. Existing continual learning techniques fall into three main categories, i.e., regularization baaaed based methods that penalize (or reward) their model objectives so as to maintain satisfactory performance on previous
38
tasks 11 26 e.g., Learning without Forgetting (LwF) (15) and Elastic Weight Consolidation
40
(EWC) 13 memory-replay based methods that constantly feed model with representative data
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

28 2 5 8 e.g., Gradient 42 or exemplars of previous tasks to prevent them from being forgotten [8
43
Episodic Memory (GEM) [ and parametric isolation based methods that adaptively introduce new parameters for new tasks and avoid the existing parameters of previous tasks heing drastically changed 25 36 35 33 Although these approaches exhibited promising performance in mitigating the problem of catastrophic forgetting in different applications, e.g., image classification, action recognition, and reinforcement learning, they are not suitable for continual graph representation learning since both the feature information and topological structure of the target node need to be considered appropriately.
44
45
46
47
48
49
50
More recently, Zhou et al. [39 proposed to store set of representative experience nodes in a buffer and replay them along with new tasks (categories) to prevent forgetting existing tasks (categories). The buffer, however, only stores node features and ignores the topological information of graphs. Liu et al. [77] developed topology-aware weight preserving (TWP) that can preserve the topological information of existing graphs. However, its design hinders the capability of learning (opology on new tasks (categories). Note that continual graph representation learning is essentially different from dynamic graph works which mainly concern time dependent graphs in which nodes and (or) edges change over time [37] 40 19]. Therefore, the methods developed for dynamic graphs cannot be directly applied to this task.
51
53
54
55
56
57
59
desired learning system for continual graph representation learning is to continuously grasp knowledge from new categories of emerging nodes and capture their topological structures without interfering with the learned knowledge over existing graphs. To this end, we present a completely novel framework, i.e., Hierarchical Prototype Networks (HPNs), to continuously extract different levels of abstract knowledge (in the form of prototypes) from graph data such that new knowledge will be accommodated while earlier experience can still be well retained. Within this framework, representation learning is simultaneously conducted to avoid catastrophic forgetting, instead of considering these two objectives separately. Specifically, based on the assumption that each node can be decomposed into basic atomic characteristics belonging to a set of attributes (e.g., gender, nationality, hobby, etc.) and the relationship between a pair of nodes can be categorized into different types (e.g. trust or distrust in a social network), we develop the Atomic Feature Extractors (AFEs) to decompose each node into two sets of atomic embeddings, i.e., atomic node embeddings which encode the node feature information and atomic structure embeddings which encode its relations to neighboring nodes within multi-hop. Next, we present Hierarchical Prototype Networks to adaptively select, compose, and store representative embeddings with three levels of prototypes, i.e., atomic- level, nove-level, and class-level. Given a new node, only the relevant AFES and prototypes in each level will be activated and refined, while others are uninterrupted. Eventually, each node can be represented with a tri-level prototypes which encode its feature as well as structure information from different abstract levels and can be used for downstream tasks such as node classification. Finally, we provide the theoretical analysis for the memory consumption upper bound of HPNs and its continual learning capability. To summarize, the main contributions of our work include:
60
81
63
64
65
67
68
69
70
71
72
73
74
75
76
77
78
We present novel framework, i.e., Hierarchical Prototype Networks (HPNs), contin- uously extract different levels of abstract knowledge (in the form of prototypes) from the graph data such that new knowledge will be accommodated while earlier well retained.
81
e experience can be
83
84
We provide the theoretical analysis for the memory consumption upper bound of HPNs and its continual learning capability.
85
86
Our experiment results on eight different public datasets demonstrate that the proposed HPNs not only achieve state-of-the-art performance, exhibiting good continual learning capability, but also use less parameters (more efficient). For instance, on OGB-Products dataset that contains more than 2 million nodes and 47 categories of nodes, HPNs achieves around 80% accuracy with only thousands of parameters.
87
88
89
90
91 2 Hierarchical Prototype Networks
92 In this section, we first state the problem we aim to study and the notations. Then we present
93 Hierarchical Prototype Networks (HPNs) that consist of two core modules, i.e., Atomic Feature
94 Extractor (AFEs) and Hierarchical Prototype Networks (HPNs), as shown in Figure AFES serve to
35 extract set of atomic features from the given graph, and the HPNs aim to select, compose, and store
96 the representative features in the form of different levels of prototypes. During the training stage, each node will only refine the relevant AFEs and prototypes of the model without interfering with the
2

---

Extabiioh na protetypes
sopp MMath to esidiin prototypes
Harrarhical
Protebpe Reoocentttion
Prototypes
Node-level Prototypes
Atomiz-hral Protonypes
Atomic Embeddings
AFE
Center
2-hop 2-300
Figure 1: The framework of HPNs. On the left, subgraphs from different tasks come in sequentially. Given node ug denotes the j-th sampled node from k-hop neighbors. the middle, node and the sampled neighbors are fed into the selected AFES to get atomic embeddings, which are either matched to existing A A-prototypes or used as new A-prototypes. The selected A- --prototypes are further matched to N- and a C-prototype for the hierarchical representation, which finally fed into the classifier perform node classification.
98 irrelevant parts (i.e., to avoid catastrophic forgetting). In the test stage, the model will activate the relevant AFES and prototypes to perform the inference.
99
100
2.1
Problem Statement and Notations
We study continual learning on graphs that have new categories of nodes and associated edges (in the form of subgraphs) emerging in continuous manner. In the context of continual learning, assuming we have a sequence of p tasks (T'i 1, ..., p). which each task T aims to learn a satisfied representation for new subgraph G; consisting of nodes belonging to some new categories. A desired model should maintain its performance on all previous tasks after being successively trained on the sequence of p tasks from T to TP.
102
103
104
105
107
For simplicity, we omit the subscripts in this section. Full notations will be used in the theoretical analysis. Each graph G consists of node set V {ryli = 1, N) with N nodes and an edge set {(u,, uy)} denoting the connections of nodes in V. Each node i; can be represented as a feature vector x(v;) E Id that encodes node attributes, e.g., gender, nationality, hobby, etc. The set of I-hop neighboring nodes of o; is defined A (vx), with (wz) (v:).
108
109
110
2.2
Atomic Feature Extractors
113
Based on the assumption that different nodes can be decomposed into basic atomic characteristics belonging to set of attributes (e.g., gender, nationality, hobby, etc.) and the relations between pair of nodes can also be categorized into different types (e.g., trust or distrust in social network), we develop Atomic Feature Extractors (AFEs) to consider two different sets of atomic embeddings,
114
115
116
117
ie., atomic node embeddings which encode the node features and atomic structure embeddings that encode its relations to neighbors within multi-hop. Specifically, to ensure that each node can be represented different combinations of a subset of atomic features, AFEs are designed as learnable linear transformations AFEnoee = (A; E [Rd E {1...., } and AFEsmmet = (R, E Rd. E (1,...,,,) 4.) where A, and R, are real matrices to encode atomic node and structure information, respectively. 1, and 1, denotes the cardinality of AFF and AFF respectively.
118
120
121
122
123
Given a node v, a set of atomic node embeddings is obtained by applying A.Epode to the feature vector x(r):
I (v) (x" (v)A, AFE
(I)
125
To obtain atomic structure embeddings, the multi-hop neighboring nodes of have be considered. We first uniformly sample fixed number of vertices from I-hop up to hthhpp neighborhood, i.e. A (w)... Then these selected nodes are embedded via projection matrices in (v) C (1
128
127
128
AFEsmet to encode different types of interactions with the target node e:
Exruct (w) = (x"(() R,), AFE E Nauu).
(2)

---

129 Finally, the complete atomic feature set of target node is:
(A(r) = F (v) U A (v).
130
Note that A, and R, are designed to generate different types of atomic features. To ensure that, we impose divergence loss on AFES ensure they are be uncorrelated with each other and thus can map features to different subspaces:
131
132
Laiv ΣATA, + ERAR.
iFj
133
2.3
Hierarchical Prototype Networks
With the atomic features extracted based AFEs, hierarchical prototype networks (HPNs) will select, compose, and store representative features in the form of different levels of prototypes as shown in Figure This is mainly achieved by refining existing prototypes and creating new prototypes only when necessary. Specifically, HPNs will produce three different levels of prototypes, i.e., atomic- level prototypes (A-prototypes), node-level prototypes (N- (N-rrotoypees), and class-level prototypes (C prottttyyess). From atomic-level to class- level, the prototypes denote abstract knowledge of the graph at different scales which is analog to the feature maps of convolutional neural networks different layers.
135
136
137
139
140
141
We first introduce how HPNs can refine existing prototypes. For each task that contains certain categories of nodes, instead of using all atomic embeddings generated by existing AFEs, HPNs only select small and fixed number of AFEs from both A and AFE which are more relevant to the given task. In this way, only the relevant AFES are refined while others remain uninterrupted. Specifically, as shown in Figure [1 given node from incoming subgraph, each AFE is used to
143
145
146
147
generate an embedding. Those AFES with embeddings that are closer to existing A-prototypes are deemed more confident ones and chosen. Formally, we first obtain Exdlee (v) and EE (v) via Eq.
148
I and Eq. (2). respectively. Then, we calculate the maximum cosine similarity between atomic
149
150
embeddings of each AFE (e:) and the A-prototypes as:
SimMAX max P
|e e EA EE) PE
(5)
151
where id E [node, struct), ranges from to la (or 1,,,, and A is the atomic prototype set containing
152
all A-prototypes. After that, we sort the AFEs in a descending order according to SimMAX as
A F FEnot = {Ar E RRdo E {1,...,4a) and AFE strucc = (R,r E Rdd xd= Jj' E
153
Finally, we select the top l", and top I/, ranked AFES from these two sets as AFE and AF
154
155
respectively. lt, and 14, are fixed hyperparameters with I/, < la and I/ < 4. The atomic embeddings generated by these selected AFES are denoted as Explect (v).
156
Based on A E HPNs then starts to distill representative features, which is conducted by refining existing prototypes and creating new prototypes simultaneously. A matching process is first conducted between the (Esclec( (u) and IP A to recognize the atomic features that are compatible with exiting A-
157
158
159
160
prototypes and those ones be accommodated with new A-prototypes. Formally, we measure the (v) and elements in PA as c
161
cosine similarity between elements in Ex
Simg-A = e, 1
le, E E (v), P PA).
(6)
162
The atomic embeddings that are compatible with existing A A-prototypes are these ones with cosine similarity not less than a certain threshold f have least one existing A-prototype, i.e.
163
oTP
Eota(e) = [cal E PA
s.t.
tx).
|e|1||||||
184 Evta(v) collects a set of atomic embeddings satisfying the previous condition and can be used to refine A- To this end, a distance loss Lais is computed to enhance the cosine similarity between 186 each e; E (v) and its corresponding A- A-prototype P; E PA..ee.
165
c. P;
Ldis
Σ
(8)
|e.l|e||P.11a
e.EZala(v)
187 By minimizing Lais, not only the existing A-prototypes in PA will get refined, the atomic embeddings will also be closer to 'standard' A-prototypes.

---

Algorithm 1: Learning Procedure for HPNs.
Input
:ask sequence: {Ti,--.. Tp), HPNs
for T to p do
2
Get the data of the current task: V. E. X(V) = (x(v)]o V).
Select AF Fuide and AFFignet
Compute C HPNN(V.X(V)A))
== HPNNsV (V)..).
Optimize L.
Output updated HPNs
189
Next, we discuss how to deal with the atomic embeddings that are not close to any existing prototypes, Le., Enew(w) (v) Ex (P)))ooa())) or Enew (v) (eel
e
170
Vp E PA.
Te. <1
Contrary to (w) atomic embeddings in Enew (v) are regarded as new atomic features of the corresponding AFEs. In this case, new prototypes should be generated accommodate them. Considering that very similar embeddings may exist in (Ene(()) and cause HPNs to create redundant prototypes, we first filter Enew (v) into (new(()) to keep only the representative ones such that
171
172
173
174
C C
Ve,, ej E Enew(()
t..
(9)
121ee22
175
Then, (u) is included into PA as new A-prototypes, which will be further refined in the future.
PA PA U (r (v).
(10)
After generating new prototypes, the matching will be conducted to get new Simg-A (v) )) in which
each element is not less than t.. Then each element in Exle (v) is assigned a closest A-prototype according to Sim Simg-~(u)) and each node is associated with set of atomic prototypes (vv).
177
178
179
To map (v) to high level prototypes so as to obtain hierarchical prototype representations. Avv) is firstly mapped to N- N-prototype denoting the overall features of c. We assume that N-prototypes lie
181
in a dn dimensional space and a fully connected layer is applied to transform ((v) into the new space (v) FCA-N (a1 @ ... @ a +1;+ ). Va, [v), where @ denotes the concatenation operator.
182
With (U), we then find a matching N-prototype or establish new one, which is similar to the process at atomic level except that the threshold is set as ÊN. instead of t... Learning class-level prototypes from node-level prototypes is same except that we set the matching threshold as to. Finally, the hierarchical prototype representations of the target node is contained in the following set (v) = A(v) U N(v) U(V).
184
186
(11)
187
Note that A(v) contains multiple A A-prototypes denoting atomic features v from different aspects. N(v) and C(r) only contain one N-prototype and one C-prototype, representing the overall character- isties of and the common characteristies shared by the community containing v. respectively.
189
190
2.4
Learning Objective
The obtained hierarchical prototypes for each node are first concatenated into unified vector and then pass through a fully connected layer FC to obtain a c (the number of classes) dimensional feature vector, i.e., FC(h; ..... he, +2,++)) Vh; E TH (v). In this paper, we aim to perform node classification. Therefore, based on the e dimensional feature vector and the softmax function o(-), we can estimate the label with 0 = (FC(h) @ ..... + hy +2)+)) where is the index of class. To perform node classification, with the output predictions & and the target label y; E {1, c), the corresponding classification loss is given by
192
198
195
196
Lote
yi log((e))
(12)
198
which is essentially the cross entropy loss function. Note that besides node classification, PH (H) may also be used for other tasks based on different objective functions. In this paper, we focus on node classification and the overall loss of HPNs is:
200
201
L Lais Ldiv Lets-
(13)
During the training stage, subgraphs with different tasks (containing different categories of nodes) continuously fed to HPNs. Note that unlike topology-aware weight preserving (TWP) method [[7],
203
HPNs do not require task indicator for training and test, and therefore is more practical for real-world continual graph representation learning applications.
205
5

---

206 2.5
Theoretical Analysis
In this subsection, we provide the theoretical upper bound for the memory consumption and analyze how the model configuration would affect HPNs' capacity in dealing with different tasks. Both theoretical results are justified and analyzed in the experiments. Only the main results are provided here, while the detailed proof and analysis are given in Appendix.
208
210
We first show that the numbers of different prototypes are upper bounded by the number of atomic feature extractors and the dimension of the prototypes. Specifically, we have:
212
213
Theorem (Upper bounds for numbers of prototypes). Given the notations defined in HPNs, the upper bound for the number of A-prototypes na can be given by
214
nA & (la + 4)) max S(da, N, tA),
(14)
N
215
and the upper bounds for the number of N-prototypes and the C-prototypes are: are:
VN & max S(dn, 1xx and TC E max N,,, N
(15)
N
where N,, is the spherical code defined on a n dimensional hypersphere (details in Appendix). 216
217
Theorem provides an upper bound for the memory consumption of HPNs. In our experiments, we show that the number of parameters for most baseline methods are even higher than this upper bound. Besides memory consumption, the more important problem for a continual learning model is the capability to maintain memory previously learned tasks. Based on our model design, we formulate this as: whether learning new tasks affect the representations the model generates for old task data. We give explicit definitions tasks and task distances based on set theory (in Appendix), then construct a bound to indicate what configuration would the model have to ensure this capability.
219
221
223
224 Theorem 2 (Task distance preserving). For HPNs trained on consecutive tasks To and T If Lada + 1,dr > (Lr + 1 yd, and W is column full rank, then as long as LA < Amiin (lr + V Vp+1), learning on T will not modify representations HPNs generate for data from TP, i.e. catastrophic forgetting is avoided.
226
1 [)dist((Vp p.
227
In Theorem []] >> is eigenvalues of the WTW, where W is matrix constructed via AFES (details in Appendix). d... dg and d, are dimensions of data and two kinds of atomic embeddings. The bound in this theorem is not tight, as the tight bound would be dependant on the specific dataset properties. But this informs us that either the number of AFES or the dimension of the prototypes has to be large enough to ensure that data from two tasks can be well separated in the representation space.
228
229
230
231
232
According Theorem 1. the upper bound of the memory consumption is dependent on S(da, N, L.). (dh,, N. W. ). and S(dze N,1c) As (m, N, grows fast with n, we prefer larger number of AFFs with smaller prototype dimensions. We also empirically demonstrate this in Section (36] Besides, the
233
234
235
236
upper bound proposed in Theorem iis explicitly computed and compared to experimental results.For both theorems, proof's and detailed explanations are included in Appendix.
237
3 Experiments
238
In the experiments, answer the following six questions: (1) Whether HPNs can outperform state-of-the-an approaches? (2) How does each component of HPNs contribute to its performance? (3) Whether HPNs can memorize previous tasks after learning each new task? (4) Are HPNs sensitive to the hyperparameters? (5) Whether the theoretical results can be empirically verified? (6) Whether the learned prototypes can be interpreted via visualization?
240
242
244
3.1
Datasets
245
To assess the effectiveness of the proposed HPNs, we consider 8 datasets which include 3 citation networks (Cora (27), Citeseer 271, OGB-Arxi 32 20). 3 web page networks (Wisconsin, Comell, Texas) [22), actor co-occurence network (Actor) [22], and product co co-purchasing networks
247
44) Detailed statistics about these datasets are provided in the Appendix.
Among these datasets, the results of 4 datasets, i.e., Cora, Citeseer, OGB-Arxiv (169,343 nodes, 1. 1,166,243 edges), and CCo-Products 12.449,029 nodes, 61,859, edges), are reported in the paper and the results of other datasets are available in the Appendix.
249
251
252
3.2 Experimental Setup and Evaluation Metries
To perform continual graph representation learning with new categories of nodes continuously emerging, we adopt a class-incremennal scheme for all datasets. Each new task brings a subgraph with new categories of nodes and associated edges, e.g., task contains classes and 2, task 2 contains
254

---

Table I: Performance comparisons between HPNs and baselines 4 different datasets.
Cora
Citeseer AM/
OGB-Arxiv
OGB-Products
C.L.T.
Base
AM/%
FMU%
FM
AM/
FM/
AM/%
/M
GCN
63,5+199
-223==04
64.5+339
-7.74:1.6
56.84443
-1.84+3.2
45.2+5.6
-27,8+7.1
None
GAT
71,94338
-33.1=233
66.8:199
-19.6:0.33
54.34:3555
21.76: 4.6
44,92699
-0033::522
GIN
68.3
33
57.742..3
36.41..33
53.2.1 6.5
23,59 188.1
43.1
-31.4.8888
GCN
1..1
1.
54.44422
-30.3+0.9
72.1424
1.1
66.7=00,5
84400.4
EWC 15
GAT
72.2-1.5
-32.2=1.6
66,7+2.5
-19.742.3
73.2
10.82211
67.9+100
-9.5+11
GIN
69.6:22.66
-28.5=288
57.94334
-3..342244
74.1 #1.
.33 #2.0
67.3+2.3
-13.6::55
LwF 15
GCN
1..1
21.31:244
67.011022
8.1.2.77
69.9
12.1128
66.3
.1.81134
GAT
2..8
-3.6-2411
66.144.11
1.5
68,9444
-136433.
65.1
-13.242299
74.1
-23.3=0.88
63.1+19
-165222
71.4 #4.8
15.945..
65.94.00
-10.743.1
GCN
3..7
66.4144
41.8:126
1.19
75.4
13.6:005
1.73
-10.5:1099
GEM
18
6..8.:3.0
26.11:26.6
71.3:1222
+.001:155
-1.3::04
70.4:08
10.9::16
GIN
3..2.13.3
2.00144
49.7.10.5
24.5.
77.3 12.1
-1...116
3..5
-7.2.12.5
GCN
1.
-21.2
59.5:13.1
-0.11:244
69.8 104
11881099
62.02111
-1799199
MAS
GAT
84.7.10.7
5.6.1..0
69.111.1
4.83333
70.6 11.
16.77 11.6
64.41..3
-1,551322
1
76.7:2266
4.00:3..6
65.2::39
+0.0::200
422
-17.0:2.33
61.4338
20.9:22999
GCN
63.5+2.4
-2,3-007
54.24399
1,
63.34-1.7
18.1
60.7+288
-6666+333
ERGN.
GAT
71.1
13
65.5:10.3
30.44399
63,5#22.4
19.5
6..3
22.11:00.8
GIN
68.3=0.4
-35.4=044
57.7+3.11
136.4
69.2 1.8
-118114
61.844.7
-23.44799
GCN
68.9-0.9
5.7.1..
60.5433.8
-0.14444
75.6410.3
10.4
69.9-0.44
1.0=
TWP
GAT
81.3+322
1,4
00.8+1.5
-8.922.66
75.8:20..5
-5.00033
69.342.3
17
GIN
73.7=332
+2.6
68.9
1,441:99
76.6+1188
-11.3111111
1..9
-10.3+22.7
0.5
0.0:1000
78.9
0.0:10.0
77.2:10.8
0.000.0
72.9112
0.0:0.00
Join.
GAT
93.9 + 0.9
0.0:10.00
79.3 + 0.8
0.0:10..0
81.8.10.3
0.0:10.00
73.7412.44
0.0:10.0
93.2 = 1.2
0.0+0.00
78.7
0.0+0..0
82.34119
0.0+0..0
77.922.1
0.0+0.00
HPNs
9.
+0.6:
79.0:10.9
-06+
85.8 0.7
+0.6:
80.1
+2.9:
AM
FM
0.02
100
3.5
Proto. dim.
001
FM 196]
10
0.00
AM
90
0,65
-0.5
14
0.00
-3.01
5
# AFEs
100 15
20
0.55
10
AFEs
15
20
0.01
0.30
0.20
&
0.30
0.40
-2.5
6.01
0.10
0,20 0.30
t
0.40
(a)
(b)
(c)
(d)
Figure 2: (a) and (b) AM and FM of HPNs with different number of AFEs and prototype dimensions on OGB-Arxiv. (c) and (d) are AM and FM change with when f. varies on Cora.
sequence of tasks, and the performance will be evaluated on all previous tasks. Specifically, we adopt accuracy mean (AM) and forgetting mean (FM) metrics for evaluation. After learning on all tasks, the AM and FM computed the average accuracy and the average accuracy decrease on all previous tasks. Negative FM indicates the existence of forgetting, zero FM denotes forgetting and positive FM denotes positive knowledge transfer between tasks. For HPNs, we set d, = dn d, 16, Lo = 4, 22, and h 2. The threshold LA.
new classes 3 and 4, etc. Each model is trained
257
259
260
251
262
Iv. and lc selected by cross validation on {0.01, 0.05, 0.1, 0.15, 0.2, 0. 0.25, 0.3, 0.35, 0.4). The experiments on the important hyperparameters are provided in Section 3.6 All experiments are run on an Nvidia Titan Xp GPU. Full implementation details are in Appendix, and the code is available
263
264
285
in supplementary materials.
286
Comparisons with Baseline Methods 3.3
267
We compare HPNs with various baseline methods, Experience Replay based GNN (ERGNN) [3 and Topology-awan Weight Preserving (TWP) [17] are developed for continual graph representation learning. The others approaches, including Elastic Weight Consolidation (EWC) B Learning with-
269
out Forgetting (LwF) [15). Gradient Episodic Memory (GEM) (18), and Memory Aware Synapses
271
(MAS) [I) are popular continual learning methods for Euclidean data. All the baselines are imple-
Table 2: Ablation study on prototypes of different levels of prototypes over Cora.
Table 3: Ablation study on different loss terms over Cora.
Conf.
App.
N.p.
C.p.
AMS
FM%
Cont.
Leta
Laco
Lace
AM%
FM%
89.24:1.3
-0.1
92441.3
+0.8+00.7
2
91.741111
-0.24:0.8
2
/
92.9=111
+0.3+:100
3
93.7
+0.6:1100
3
d
92.2099
+0.0:11.22
4
ff y
/
93,7=1.5
+0.6::1000
7

---

6400
1.00
1800
N-Proto. Proroo. C-Proto.
Prototypes
Parameters
0.95
1350
ARS
0.90
900
4700
HPNs
0.85
GAT
450
# Para.: Upper bound
TWP+GAT
# Para:: Actual
0.80
10
15
20
0.01
0.10
0.20
0.30
0.40
3000
10
15
20
Tasks
f
Tasks
Figure 3: Left: dynamics of ARS for continual learning tasks on OGB-Arxiv. Middle: impact of LA the
number of prototypes in HPNs Cora. Right: dynamics of memory consumption of HPNs OGo-Products.
Table 4: Final parameter amount for models trained on CGB-Products
Nooe
EWC
LwF
GEM
MAS
ERGNN
TWP
Joint
HPNs
GCN
2.336
46,720
4,672
2,202.336
2.336
6,738
9,344
2,336
GAT
20,032
400.640
40,064
2,220,032
20.032
24,432
80.128
20,032
4,908
2,352
47,040
4,704
2,202,352
6,752
9,408
2,352
272
mented based on three popular backbone models, i.e., Graph Convolutional Networks (GCNs) [2] Graph Attentional Networks (GATs) [31], and Graph Isomorphism Network (GIN) [3]..
273
274
Note that Joint training (Join.) in Table d does not represent continual learning. It allows model to access data of all tasks any time and thus is often used as an upper bound for continual learning. 29
275
In T we observe that regularization based approaches, e.g., EWC and TWP, generally obtain lower forgetting, but the accuracy (AM) is limited by the constraints. However, the forgetting problem of regularization based methods will become increasingly severe when the number of tasks is relatively large, as shown in Section 3.5 Memory replay based methods such as GEM achieve better performance without using any constraint. However, the memory consumption is higher (Section (37). HPNs significantly outperform all baselines without inheriting their limitations. Compared to regularization based methods, HPNs do not impose constraints to limit the model's expressiveness, therefore the performance is much better. Compared to memory replay based methods,
277
279
281
282
283
284
HPNs do not only perform better but also are memory efficient shown in Section 3.7 Joint training (Join.) achieves comparable performance to HPNs on small datasets but is significantly worse on large
285
OGB datasets. This is because joint training (Join.) is multi-task setting, inter-task interference 286
287
may cause negative transfer, which is not obvious on small datasets with only few tasks but becomes prominent on large datasets with tens of tasks. In HPNs, different tasks can choose different combinations of the parameters and thus task interference is dramatically alleviated.
288
289
290
3.4
A Ablaioon Study
291
We conduct ablation studies on different levels of prototypes and different combinations of three loss terms. In Table 2 we show the performance of HPNs when A-, N-, and C-Prototypes are gradually added (Cora dataset). We notice both AM and FM of HPNs increase when higher level prototypes are considered. This suggests that high level prototypes can enhance the model's ss performance and robustness against forgetting. The effect of different combinations of loss terms are shown in Table 3
292
293
294
295
296
The first three rows show that adding Laiv or Lais with Late may slightly improve the performance. By jointly considering these three terms, the performance (AM) can be further improved. This is because Lain pushes different AFEs away from each other and Lais makes the prototypes of each
297
299
AFE be more close to its output. Jointly considering Lase and Laie with Lote can make the prototype
space better separated as shown in Section 3.8
3.5
Learning Dynamics
302
For continual learning, it is important to memorize previous tasks after learning each new task. To measure this, instead of directly measuring the average accuracy on previous tasks which may mix up the accuracy change caused by forgetting and task differences, we develop a new metric, i.e., average retaining score (ARS), to address this problem. Specifically, after learning on a task T', the ratio between the model's accuracy on a previous task T and its accuracy on 7 after it had been just learned on 7 is defined as the retaining ratio. Then the ARS is the average retaining ratio of all previous tasks after learning new task.
303
305
307
Figure Ieff) shows the ARS change of HPNs and two baselines. GAT represents the models without continual learning techniques. TWP+GAT is the best baseline in terms of forgetting. GAT forgets quickly, while TWP significantly alleviates the forgetting problem for GAT, But as more tasks come in, the forgetting of TWP+GAT increases. As different tasks require different parameters, TWP+GAT
309
311
312
8

---

Class 0
Class
Class
30-
20
Class
20
10
10-
-20
-70
-20
Class
-30
-30
Cleck
Class
-20
-10 10
-30
-20 -10 10 20
-10 10
20
Figure 4: Visualization of hierarchical prototype representations of nodes in the test set of Cora.
313
(regularization based) is seeking a trade off between old and new tasks. With more new tasks, TWP+GAT tends to gradually adapt new tasks and forget old ones. On contrary, HPNs maintain the ARS very well. This is because HPNs learn prototypes to denote the common basic features and learning new tasks does not hurt the parameters for old tasks. New tasks can be handled with new combinations of the existing basic prototypes. If necessary, new prototypes can be established for more expressiveness.
315
316
317
3.6
Parameter Sensitivity
320
As discussed in Section 2.5 the number of AFEs and the prototype dimensions are key factors in determining the continual learning capability and memory consumption. Here, we conduct experiments with different number of AFEs and prototype dimensions to justify the theoretical results. We keep the dimensions of different prototypes equal and the number of two types of AFEs equal for simplicity.
321
322
323
324
As shown in Figure a and (b), larger dimensions and the number of AFEs yield better AM and FM, which is consistent with Theorem Besides, AM is mostly determined by the number of AFEs
325
328
327
since HPNs compose prototypes with different AFEs to represent each target node. The number of possible combinations determines its expressiveness. Considering the above results and the bound
328
329
[Theorem] IT for the number of prototypes, using large number of AFEs and small dimension can ensure both high performance and low memory usage, verified in Section 3.7
331
We also evaluate the effectiveness of HPNs when prototype thresholds vary from 0.01 to 0.4. Here, we set tA = tv = to for simplicity. In Figure ( and (d), we observe that the performance (AM and FM) of HPNs are generally stable when tA varies and slightly better when t. between
332
333
334
0.2 and 0.3. This is because when t is too small or too large, we will have too many or too less prototypes (consistent with Theorem I as shown in Figure [3] middle), which may cause the problem of overfitting or underfiting.
335
3.7
Memory Consumption
We compare memory consumption of different methods, as well as explicitly theoretical memory upper bound, with the baselines on CGB-Products (the largest dataset). We also show the actual memory consumption of HPNs in the process of continual learning.
339
341
In Table even on the dataset with millions of nodes and 23 tasks, HPNs can accommodate all tasks with small amount of parameters. Besides, the dynamic change of parameter amount is shown in EegureBright The red dashed line denotes the theoretical upper bound (6, 163), and the computation details are included in Appendix. In Figure rright), we notice the actual memory usage of HPNs is much lower than the upper bound. Moreover, even the upper bound among the lowest for memory consumption compared to baselines. The model we use here is the same the one in Section 3.3
342
343
345
3.8
Visualization
348
To show that HPNs can generate interpretable prototype representations, we apply t-SNE 30 to visualize the node representations of the Cora dataset (test set) after learning each task. As shown in
349
350
Figure each task contains two classes corresponding to (red, blue), (green, salmon), and (purple, orange), new tasks come in gradually, the representations are consistently well separated, which will be beneficial for downstream tasks.
351
352
Conclusion
353
354
In this paper, we proposed Hierarchical Prototype Networks (HPNs), to continuously extract different levels of abstract knowledge (in the form of prototypes) from streams of tasks on graph representation learning. The performance of HPNs is both theoretically and experimentally justified. In the future,
355
357 we will apply HPNs to more application scenarios like link prediction, multi-label classification, anomaly detection, etc.

---

References
359
360
[1] Rahaf Aljundi, Francesca Babiloni, Mohamed Elhoseiny, Marcus Rohrbach, and Tinne Tuyte- laars. Memory aware synapses: Learning what (not) to forget. In Proceedings of the European Conference on Computer Vision (ECCV), pages 154, 2018.
362
383
[2]
Rahaf Aljundi, Min Lin, Baptiste Goujaud, and Yoshua Bengio. Gradient based sample selection for online continual learning. In Advances in Neural Information Processing Systems, pages 1 11816-11825, 2019.
364
365
[3]
Smriti Bhagat, Graham Cormode, and S Muthukrishnan. Node classification in social networks In Social network data analytics, pages 115-148. Springer, 2011.
387
388
[4] K. Bhatia, K. Dahiya, H. Jain, P. Kar, A. Mittal, Y. Prabhu, and M. Varma. The extreme classification repository: Multi-label datasets and code, 2016.
389
370
[5] Lucas Caccia, Eugene Belilovsky, Massimo Caccia, and Joelle Pineau. Online learned continual compression with adaptive quantization modules. In International Conference on Machine Learning, pages 1240-1250 PMLR, 2020.
372
373
[6] Jie Chen, Tengfei Ma. and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint 1801 10247, 2018.
374
375
[7] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learming, pages 1725-1735. PMLR, 2020.
377
378
[8] Aristotelis Chrysakis and Marie-Francine Moens. Online continual learning from imbalanced data. In International Conference on Machine Learning, pages 1952-1961. PMLR, 2020.
379
380
99 Mehrdad Farajtabar, Navid Azizan, Alex Mott, and Ang Li. Orthogonal gradient descent for continual learning. In International Conference on Artificial Intelligence and Statistics, pages 3762-3773. PMLR, 2020.
382
383
[10]
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pages 1024-1034, 2017.
384
385
Heechul Jung. Jeongwoo Ju, Minju Jung, and Junmo Kim. Less-forgetting learning in deep neural networks. arXiv preprint arXiv: 2016.
[12] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional 2016.
388
networks. arXiv preprint
389
[13] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Barriikk,, et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 1 114(13):55113352, 2017
390
391
392
393
[14] Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep cnns? In Proceedings of the IEEE International Conference on Computer Vision, pages 9267-9276, 2019.
395
396
[15] Zhizhong Li and Derek Hoiem. Learning without forgetting. IEEE transactions on pattern analysis and machine intelligence, 40(12):2935 2947, 2017.
397
398
[16] David Liben-Nowell and Jon Kleinberg. The link fnk-prediction problem for social networks. Journal of the American society for information science and technology, 58(7)1019-1031, 2007.
400
401
[17] Huihui Liu, Yiding Yang, and Xinchao Wang. Overcoming catastrophic forgetting in graph neural networks. arXiv preprint arXiv:2012.06002, 2020.
402
403
[18]
David Lopez-Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continual learning. In Advances in neural information processing systems, pages 6467-6476, 2017.
10

---

405
[19] Yao Ma, Ziyi Guo, Zhaocun Ren, Jiliang Tang, and Dawei Yin. Streaming graph neural networks. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 719-728, 2020.
406
408
[00] Tomas Mikolov, lly Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionality. arXiv preprint arXiv: 1010.11144444 10.4546.
409
410
2013.
411
[21] Giang Hoang Nguyen, John Boaz Lee, Ryan A Rossi, Nesreen K Ahmed, Eunyee Koh, and Sungchul Kim. Continuous-timm dynamic network embeddings. In Companion Proceedings of the The Web Conference 2018, pages 969-976, 2018.
413
[22] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
415
416
[23] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
417
418
419
[24] Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: graph convolutional networks on node classification. In International Conference on Learning Representations, 2019.
Towards deep
420
422
[25] Andrei A Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. arXiv preprint arXiv:1606.04671 2016.
424
[26] Gobinda Saha and Kaushik Roy. Gradient projection memory for continual learning. In International Conference on Learning Reprexentation, 2021.
426
427
[27] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
428
429
[28] Hanul Shin, Jung Kwon Lee, Jaehong Kim, and Jiwon Kim. Continual learning with deep generative replay. In Advances in neural information processing systems, pages 2990-2999, 2017.
431
[29] Gido M Van de Ven and Andreas S Tolias. Three scenarios for continual learning, arXiv preprint arXiv:1904.07733 2019.
433
434
[30] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, (11). 2008
435
436
[31] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint 1700 2017.
438
[32] Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chich-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396-41,, 2020.
440
(33] Mitchell Wortsman, Vivek Ramanujan, Rosanne Liu, Aniruddha Kembhavi, Mohammad Rastegari, Jason Yosinski, and Ali Farhadi. Supermasks in superposition. arXiv preprint arXiv:2006. 14769, 2020.
442
443
444
[34] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.0088 2018.
445
[35] Jachong Yoon, Sachoon Kim, Eunho Yang, and Sung Ju Hwang. Scalable and order-robust continual learning with additive parameter decomposition. In International Conference on Learning Representation, 2020.
447
449
[36] Jaehong Yoon, Funho Yang, Jeongtae Lee, and Sung Hwang. Lifelong learning with dynamically expandable networks. arXiv preprint 11X1v 2017.
11

---

451
[37] Wenchao Yu, Wei Cheng, Charu C Aggarwal. Kai Zhang, Haifeng Chen, and Wei Wang. Netwalk: A flexible deep embedding approach for anomaly detection in dynamic networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2672-2681, 2018.
452
453
454
455
[38]
Xikun Zhang, Chang Xu, and Dacheng Tao. On dropping clusters to regularize graph convolu- tional neural networks. 2020.
456
457
[39] Fan Zhou, Chengtai Cao, Ting Zhong, Kunpeng Zhang. Goce Trajcevski, and Ji Geng. Continual graph learning. arXiv preprint arXiv:2003. 09908, 2020.
458
[40] Lekui Zhou, Yang Yang, Xiang Ren, Fei Wu, and Yueting Zhuang. Dynamic network embedding by modeling triadic closure process. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
460
462
[41] Difan Zou, Ziniu Hu, Yewen Wang. Song Jiang. Yizhou Sun, and Quanquan Gu. Layer- dependent importance sampling for training deep and large graph convolutional networks. In Advances in Neural Information Processing Systems, pages 1247-11256, 2019.
464
Checklist
485
486
1. For all authors...
467
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
468
(b) Did you describe the limitations of your work? [Yes] In Conclusion, and in the theoretical part of Appendix.
470
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work solves the continual graph representation learning problem. As far as we know, there is no potential negative societal impacts of our work.
472
474
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
475
478
2. If you are including theoretical results...
477
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Details are included in Appendix.
478
479
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs are in Appendix
480
3. If you ran experiments...
481
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as URLY? [Yes] Code is included in the supplementary materials.
482
483
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Details are included in Appendix.
485
486
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] In all tables and in Figure
487
488
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] Relevant details are included in Appendix
490
491
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
492
(a) If your work uses existing assets, did you cite the creators? [Yes]
483
(b) Did you mention the license of the assets? [Yes] We mentioned this in the dataset detail part Appendix.
494
495
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes] The code of our model is included in the supplementary materials.
497
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] We mentioned this in the dataset detail part in Appendix.
12

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [Yes] We mentioned this in the dataset detail part in Appendix.
500
802
5. If you used crowdsourcing or conducted research with human subjects...
503
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
505
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
506
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
508
13


Reviews:
[{"review_id": "w_6Y0GRE5x", "reviewer": "Reviewer_eRkd", "summary": "This paper introduces continual learning in graph settings, where new graph-based tasks come in over time. To learn effective node classifiers for new tasks without forgetting the old tasks, a three-level prototype network is outlined. Atomic, node, and class prototypes are jointly used on top of Atomic Feature Extractors, where only the relevant features and prototypes are selected and updated in each new task, without disturbing the others. Experiments on eight benchmarks show the effectiveness and lack of forgetting for continual node classification.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[Strengths]\n\nThis paper addresses a challenging task in graph learning, namely the scenario where new graph tasks come in over time. The proposed multi-level approach is interesting at a high level as it addresses different levels of granularity.\n\nThe paper furthermore excels at outlining current advances in continual learning and specifically in the graph context. This outline helps not only with providing the proper background and starting point of this paper, but also helps to understand what is new here.\n\nThe presented results show that the approach not only obtains a high accuracy overall, but at the cost of minimal loss of accuracy with the introduction of new tasks. These results highlight the potential of the proposed approach.\n\n[Weaknesses]\n\nThere are a number of limitations to the paper that require addressing.\n\nFirst, the method is not written well and unnecessarily hard to go through. Section 2 contains many unintuitive steps and unclear notations that make it hard to understand what is going on. For example:\n- What is the idea behind subsampling the neighbourhood in lines 125-127?\n- According to Equation 3, the node v is represented by a set of features, both from node and structure information. Why are these two sets combined in Equation 3 and separated again in Equation 5? And how do you go from AFE_{node}^{select} and AFE_{struct}^{select} to \\mathbb{E}_A^{select}(v)?  There is no explanation and completely unclear.\n- What is the point of Algorithm 1? It contains so few steps that there is no information anymore. Steps 4 and 5 are the same too.\n- Where does \\mathbb{A}(v) magically come from in line 178? What does associated with mean? And how big is the set  for each node? Again not clear from the method section.\n- The N-prototypes are obtained from \\mathbb{A}(v), and C-prototypes are obtained from N-prototypes. What does Equation 11 mean in that case? How can you throw them on one pile?\n- At the end, there is a cross-entropy objective in Equation 12, where the likelihoods are obtained from a fully-connected layers that takes inputs from all levels of prototypes. Don’t the prototypes have different dimensionalities however? What is going on on lines 193 and 195?\n\nNext to the mathematical explanation, the writing also requires improvement. A few examples from Section 2.4 and 2.5 (not a full list):\n- Line 192: pass = passed\n- Line 203: unlike topology-aware = unlike the topology-aware\n- Line 204: HPNs do not require task indicator = HPNs not require a task indicator\n- Line 228: is = denotes the / are the\n\nSection 2.5 provides two theorems, but the appendix only provides a proof for Theorem 2. Where is the proof for Theorem 1?\n\nIn the experiments, Table 1 shows that the proposed approach outperforms all other approaches. Where do the numbers of the baselines come from? Baseline [39] should btw be updated to:\n\n[a] Zhou, Fan, and Chengtai Cao. \"Overcoming Catastrophic Forgetting in Graph Neural Networks with Experience Replay.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 5. 2021.\n\nIn [a], they report a best PM of 95.66% and 81.83% on Cora and Citeseer, compared to 93.7% and 79.0% for this paper. Notably, [39] obtains only 71.1% and 65.5%. How come there are such big differences between what is reported in the original paper and what is reported in Table 1? Table 1 suggest that the proposed approach is far better than the baselines, while a direct comparison between papers suggests otherwise.\n\n[Overall]\n\nThis paper addresses a challenging task with a multi-level approach. The method is intuitive at a high level and the related work is outlined well. The method section itself can however hardly be followed and requires big changes. Experimentally, there are also open questions that require attention regarding reported numbers.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main limitation that is discussed is that only node classification is investigated. The checklist states that there are no negative societal impacts of the work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "k0yf2jGL38", "reviewer": "Reviewer_9787", "summary": "This paper addresses graph representation learning in a particular online/continual/streaming setting in which subgraphs are sequentially recieved which may contain nodes of categories/classes that haven't been seen before, while performance on the previously seen categories/classes must be maintained.  The approach involves extracting \"atomic\" features based on node features and local network structure, then constructing and maintaining prototype embeddings at various levels of abstraction, in order to produce a final embedding to be used by a node classifier. In each iteration the method decides whether to introduce new prototypes based on matching to previous prototypes. The authors prove a bound on the number of prototypes (hence, memory requirements) and show that the method will avoid catastrophic forgetting. Experimental results versus various baselines are positive.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nOriginality: While graph representation learning has been heavily studied, including substantial work on temporal/dynamic networks, and continual/online learning has also received significant attention, the particular setting addressed in the paper is an interesting special case of the problem.  The proposed method has not been considered before, but it is not clear that broader insights arise from, or underpin, its development.  \n\nQuality: Although intuitively appealing, the proposed model design is somewhat heuristic in nature.  It is unclear what fundamental principles motivate the use of prototypes or the various algorithmic choices which were made.  At least, the theoretical results in Section 2.5 show that the proposed method avoids certain pitfalls, but they do not otherwise guarantee how close to optimal the predictions are (e.g., in terms of regret).  The experimental results are a strength of the work, including good results in a systematic cross-validation-with-hyperparameter-tuning experiment compared to a number of baselines on multiple datasets, an ablation study, memory consumption, and t-SNE visualizations.\n\nClarity: The paper can be understood, with some effort.  There are relatively few typos or grammatical issues.  Figure 1, explaining the method, is helpful in understanding the approach.\n\nSignificance: The strong experimental results suggest that the proposed method is an improvement over the current state of the art at this particular representation learning problem, which may have practical importance.  However, the heuristic nature of the approach does not suggest that the ideas here will have influence beyond the narrow task, or will stand the test of time.\n\n------\n\nThanks to the authors for their detailed and well argued rebuttal. The response was helpful for understanding how the authors perceive the points I've raised.   I have no problem with the hierarchical prototype approach proposed here, but I don't really see an overarching objective or motivating principle that spans both the matching prototypes phase and the learning phase, each of which seems to have unrelated objectives.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Graph representation learning can be subject to algorithmic bias/fairness issues.  It would be worth mentioning how this might be addressed in future work.\n", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns were identified.\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "g9iB69I9NKQ", "reviewer": "Reviewer_eQnQ", "summary": "This paper aims to address the catastrophic forgetting issue with continual learning on streaming graphs. To comprehensively incorporate the feature and topological information of new nodes, this paper proposes atomic feature extractors to project raw node features and neighbor nodes into distinct base embeddings, which are then used to refine or compose atomic-, node-, and class-level prototype embeddings in a hierarchical manner. Experiments demonstrate that by doing so, catastrophic forgetting can be avoided and promising accuracy can be achieved on continual graph learning tasks.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The highlights of this paper are as follows:\n1. The proposed approach is well motivated, where the compositional node embeddings based on hierarchical prototypes is able to make the approach scalable to larger datasets.\n2. Despite some syntax errors, the presentation of this paper is overall clear and easy to follow.\n3. The experimental evaluations are thorough, spanning across a wide range of heterogeneous graph datasets, and most technical claims are backed by the results.\n\nAt the same time, several shortcomings of this paper are also noticed, which are listed below:\n1. The parameter-saving claim only holds when the input node features do not include node IDs, where the AFEs only need to perform transformations on the low-dimensional feature vectors. In some other graph learning settings where node IDs are used as the input feature, AFEs will essentially be multiple node embedding tables where $d_v$ is the total number of nodes, which will dominate the parameter size and become less scalable than other methods that only maintain one node embedding table.\n2. Equations 5,6,7,8 need 4 repetitive computations of pairwise cosine similarity between atomic features and the prototype embeddings, which can be very time-consuming given the potential size of set $\\mathbb{P}$. Is the approach able to reuse results from previous steps (e.g., Eq 5) to cut the time cost?\n3. The atomic features are refined by a hard selection process with pre-defined threshold. While the learning process seems to be end-to-end in Algorithm 1, it remains unclear how the hard selection of atomic features is made differentiable to allow for end-to-end training. \n4. The overall learning objective directly combines three loss functions without any coefficients to balance any part of the sub-losses, which is uncommon. It is expected to provide more details and justifications on doing so.\n5. As mentioned above, several syntax errors are found in this paper:\n- Incomplete sentences: Figure 1 --> “Given a node v”; Section 2.3 --> “To map … prototype presentations.”; \n- Section 2.2., “they are be uncorrelated” --> are uncorrelated\n- Section 2.3, “HPNs then starts to” --> start\n- Section 2.3, “a N-prototype” --> an\n\nIn summary, the highlights of this paper outweighs its shortcomings, while this paper can still benefit from some clarifications on the issues listed above.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of this paper are mainly associated with the lack of detailed explanations w.r.t. some technical claims, and the authors are recommended to provide more corresponding justifications. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "dIN8eXcHvAl", "reviewer": "Reviewer_E15x", "summary": "The paper addresses the continuous representation learning problem for graph data. The main goal is to learn emerging novel node categories, and simultaneously maintain the learned knowledge over existing graphs. In the proposed solution called Hierarchical Prototype Networks (HPNs), several levels of general knowledge are extracted, in the form of atomic, node and class-level prototypes. A theoretical analysis for the memory consumption and continual learning capability is presented. Empirical study is conducted  on eight different public datasets, including large-scale datasets with millions-scale nodes.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points\n\n- The paper addresses an important, well motivated problem in graph representation learning with practical significance. \n\n- The presentation is largely clearly. \n\n- Experiments are fairly comprehensive, including results on large-scale graphs.\n\nWeak points\n\n- There is some similarity to few-shot learning on graphs [a,b], although they mostly focus on novel class only without considering how the performance of existing classes are maintained. Nevertheless, discussion and comparison with few-shot methods should be included, to highlight the advantage of HPN over few-shot methods.\n\n[a] Meta-GNN: On Few-shot Node Classification in Graph Meta-learning. CIKM19\n\n[b] Relative and Absolute Location Embedding for Few-Shot Node Classification on Graph. AAAI21.\n\n- Hierarchical graph representation learning has also been explored [c,d], which is more flexible/self-adaptive than the 3-level prototypes in this paper.  \n\n[c] Hierarchical graph representation learning with differentiable pooling. In NIPS 2018\n\n[d] Graph Few-shot Learning via Knowledge Transfer. AAAI20.\n\n- The model involves a number of hyperparameters related to the thresholds/number of candidates, including l_a, l_r, l'_a, l'_r, t_A, t_N, t_C. This would make model tuning slow and impractical. It is also possible that, as novel classes emerge, these hyperparameters may not to change as well for optimal performance.\n\n- Message passing GNN is considered SOTA on graph data. The proposed solution derives representations from multi-hop neighbors, lacking the recursively defined message passing mechanism. A discussion on this is needed to demonstrate the design advantages and disadvantages of HPN.\n\n-- update after rebuttal --\n\nBased on the rebuttal, i have increased my rating slightly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Fine with me.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses graph representation learning when new categories of nodes emerge continually along with their associated edges. The idea is to learn a Hierarchical Prototype Networks (HPNs) which extract prototypes at different levels (atom, node, class) to represent the continually growing graphs. This allows updates to focus on relevant prototypes and atomic feature extractors. Analysis on memory consumption is given, along with continual learning capability.

Although the proposed approach is a bit ad hoc, it has interesting ideas and the empirical performance looks fine.  Three major drawbacks are identified by the reviewers, and I agree with them. Firstly, the presentation can be improved to clarify the motivation, and to provide an overarching objective or motivating principle that spans both the matching prototype phase and the learning phase (quote Reviewer 9787).  Section 2.2 and 2.3 read very dry, and Reviewer eRkd provided very detailed comments.  Secondly a detailed discussion on the large number of hyperparameters is needed.  Finally, although [c, d] raised by Reviewer E15x do not directly work on continual learning, the few-shot nature makes such adaptation quite straightforward.  A detailed comparison is needed on such extensions.

All reviewers except the most positive one (eQnQ) participated in discussions that are not visible to the author.

Minor: 
Equation 4 needs to reduce to a scalar
Algorithm has duplicated lines 4 and 5
Decision: Reject