Sufficient Subgraph Embedding Memory for Continual Graph Representation Learning
Authors: Xikun ZHANG
Dongjin Song
Dacheng Tao
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph
Class-incremental learning
continual learning
network

Abstract: Memory replay, which constructs a buffer to store representative samples and retrain the model over the buffer to maintain its performance over existing tasks, has shown great success for continual learning with Euclidean data. Directly applying it to graph data, however, can lead to the memory explosion problem due to the necessity to consider explicit topological connections of representative nodes. To this end, we present Parameter Decoupled Graph Neural Networks (PDGNNs) with Sufficient Subgraph Embedding Memory (SSEM) to fully utilize the explicit topological information for memory replay and reduce the memory space complexity from $\mathcal{O}(nd^L)$ to $\mathcal{O}(n)$, where $n$ is the memory buffer size, $d$ is the average node degree, and $L$ is the range of neighborhood aggregation. Specifically, PDGNNs decouple trainable parameters from the computation subgraphs via $\textit{Sufficient Subgraph Embeddings}$ (SSEs), which compress subgraphs into vectors ($\textit{i.e.}$, SSEs) to reduce the memory consumption. Besides, we discover a $\textit{pseudo-training effect}$ in memory based continual graph learning, which does not exist in continual learning on Euclidean data without topological connection ($\textit{e.g.}$, individual images). Based on the discovery, we develop a novel $\textit{coverage maximization sampling}$ strategy to enhance the performance when the memory budget is tight. Thorough empirical studies demonstrate that PDGNNs with SSEM outperform state-of-the-art techniques for both class-incremental and task-incremental settings. 

Under review as a conference paper at ICLR 2023
SUFFICIENT SUBGRAPH EMBEDDING MEMORY FOR CONTINUAL GRAPH REPRESENTATION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Memory replay, which constructs buffer to store representative samples and re- train the model over the buffer to maintain its performance over existing tasks, has shown great success for continual learning with Euclidean data. Directly applying it to graph data, however, can lead to the memory explosion problem due to the necessity to consider explicit topological connections of representative nodes. To this end, we present Parameter Decoupled Graph Neural Networks (PDGNNs) with Sufficient Subgraph Embedding Memory (SSEM) to fully utilize the explicit topo- logical information for memory replay and reduce the memory space complexity from (nd" to On)), where is the memory buffer size, is the average node degree, and L is the range of neighborhood aggregation. Specifically, PDGNNs decouple trainable parameters from the computation subgraphs via Sufficient Sub- graph Embeddings (SSEs), which compress subgraphs into vectors (i.e., SSEs) to reduce the memory consumption. Besides, we discover a pseudo-training effect memory based continual graph learning, which does not exist in continual learning on Euclidean data without lopological connection (e.g., individual images). Based the discovery. develop novel coverage maximization sampling strategy to enhance the performance when the memory budget is tight. Thorough empir- ical studies demonstrate that PDGNNs with SSEM outperform state-of-the-art techniques for both class-incremental and task-incremental settings.
INTRODUCTION
Continual graph representation learning (Liu et al. 2021 Zhou & Cao 2021 Zhang et al., 2021) which aims to accommodate new types of emerging nodes in graph and their associated edges without interfering with the model performance over existing nodes, is an emerging area that attracts increasingly more attention recently. It exhibits enormous value in various practical applications, especially in the case where graphs are relatively large and retraining a new model over the entire graph is computationally infeasible. For instance, in a social network, community detection model has to keep adapting its parameters based on nodes from newly emerged communities; in citation network, document classifier needs continuously update its parameters to distinguish the documents of newly emerged research fields.
Memory replay (Rebuffi et al. 2017 Lopez-Paz & Ranzato 2017 Aljundi et al. 2019 Shin et al. 2017), which stores representative samples in buffer for retraining the model to maintain its performance over existing tasks, exhibits great success in preventing catastrophic forgetting for various continual learning tasks, e.g., computer vision and reinforcement learning (Kirkpatrick et al.)
2017 Li & Hoiem] 2017 Aljundi et al., 2018 Rusu et al. 2016). Directly applying memory replay graph data with message passing based graph neural networks (GNNs) (Gilmer al. 2017 Kipf & Welling 2016 Veličković et al. 2017). however, could give rise to the memory explosion problem. Specifically, due to the message passing over the topological connections in graphs, retraining an L-layer GNN (Figure a) with buffered nodes would require storing O(nd*) nodes (Chiang et al. 1019,
2019 Chen et al. 2017) (the number of edges is not counted yet) the buffer, where d is the average node degree. Take the Reddit dataset (Hamilton et al., 2017) for an example, its average node degree 492, the buffer size will easily be intractable even with a 2 layer GNN. To overcome this issue, Experience Replay based GNN (ER-GNN) (Zhou & Cao 2021 stores representative nodes in the buffer but completely ignores the topological information (Figure I b). Feature graph network (FGN) (Wang et al.] (2020a) implicitly encodes node proximity with the inner products between the features of the target node and its neighbors. However, the explicit topological connections are completely ignored and message passing is no longer feasible on the graph.

---

Under review as a conference paper at ICLR 2023
Computation Subgraphs
Sample & Store
Choices of Buffer
Computation Subgraphs
SSEM
Replay
Butter
14
Subgraph Buffer
Coverage
Sampes & Store
Ratio
Neighorhood Adtrepation
Feature ionftomationn
Haihhooroood Agragaatinn
Thansfommatio conooormationn
Replay
Predictio
(a)
55E Generatio
Sufficient
Triinatle Function
Function
lope(( (.))
Subgraph
()
Prediction
Single Node Buffer
Embeddingg
fooll
1.ayer
(b)
(c)
Figure 1: (a) Directly storing computation subgraphs for replay in a multi-layer MPNN. (b) The strategy to store single nodes proposed in ER-GNN (Zhou & Cao. (02T). (C) Our PDGNNs with SSEM. The incoming computation subgraphs are first embedded as SSEs and then fed into the trainable function. The SSEs are sampled and stored with the probability computed based on their coverage ratio, ie., the ratio of nodes covered by their computation subgraphs (Section 3.6
To this end, we propose Parameter Decoupled Graph Neural Networks (PDGNNs) with Sufficient Subgraph Embedding Memory (SSEM) for continual graph learning. Since the key challenge lies in the unbounded sizes of the computation subgraphs, we introduce the concept of Sufficient Subgraph Embedding (SSE) with a fixed size but contains all necessary information of a computation subgraph for model optimization. Such SSEs can be surrogates of computation subgraphs memory replay. Next, we found that it is infeasible to derive SSEs from MPNNs since their trainable parameters and individual nodes/edges are entangled. To this end, we formulate the PDGNNs framework to decouple them and enable memory replay only based on buffered SSEs (without the computation subgraphs). Since the size of an SSE is fixed, the memory space complexity of a buffer with size n can be dramatically reduced from O(nd") to (()). Moreover, different from traditional continual learning on data without topology (e.g., images), we discover that replaying an SSE incurs a pseudo- training effect the neighbor nodes, which strengthens the prediction of the other nodes in the same computation subgraph. This effect is unique in continual graph learning and takes place due to the neighborhood aggregation in GNNs. We further analyze that in homophilous graphs (prevalent in real-world data), the pseudo-training effect makes the SSEs corresponding to larger computation subgraphs (quantitatively measured by coverage ratio) more beneficial to continual learning. Inspired by this, we develop a novel coverage maximization sampling, which enlarges the coverage ratio of the selected SSEs and empirically enhances the performance without consuming additional memory. In experiments, we adopt both the class mlassinncremenal (class-II.) continual learning scenario (Rebuffi) ctt al., (017) (rarely studied for node classification under the continual learning setting) and the fask-incemmental (task-IL) scenario (Liu et al. [222]] Zhou & Cao 2021p. Thorough empirical studies demonstrate that PDGNNs with SSEM outperform state-of-the-an continual graph representation learning techniques for both class-IL and task-IL settings. Our contributions are summarized below:
We formulate the framework of PDGNNs-SSEM, which successfully enable memory replay with topological information for continual graph representation learning, and reduce the memory space complexity from Ondd)) to (n)).
PDGNNs-SSEM obtain superior performance especially in the challenging class-IL II scenario. We theoretically reveal unique phenomenon in continual graph learning (i.e. the pseudo- training effect) when applying memory replay, and accordingly develop the coverage maximization sampling strategy to leverage this effect for improving the performance.
2 RELATED WORKS
Our proposed PDGNNS- is closely related to continual learning, continual graph learning, and decoupled graph neural networks.
2.1 CONTINUAL LEARNING & CONTINUAL GRAPH LEARNING
To alleviate the catastrophic forgetting problem encountered by machine learning models, i.e., drastic performance decrease previous tasks after learning new tasks, existing approaches can be categorized into three types. Regularization based methods apply different constraints to prevent drastic modification of model parameters that important for previous tasks (Farajtabar et al. 2020 Kirkpatrick et al.] 2017: Li & Hoiem| 2017: Aljundi et al. 22118) Hayes & Kanan] (020). Parametric isolation methods adaptively allocate new parameters for the new tasks protect the parameters for
2

---

Under review as a conference paper at ICLR 2023
2017 Rusu et al. the previous tasks (Wortsman et al. 2020: Wu et al., 2019b; Yoon et al.
2020:
2016). Memory replay based methods alleviate forgetting by storing and replaying representative data examples from previous tasks when learning new tasks (Caccia et al. 2020 Chrysakis & Moens 2020
Rebuffi et al. 2017: Lopez-Paz & Ranzato 2017: Aljundi et al. 2019) SShin et al. 2017). Recently,
continual learning graphs attracts increasingly ly more attention due its practical importance (Zhou
& Cao 2021; Zhang et al. [222]: Liu et al., 2021; Wang et al. 2020b; Xu et al. 2020 Daruna et al.
2021p. Existing works include regularization methods like topology-aware weight preserving (TWP)
(Liu et al., 2021 to preserve crucial parameters and topologies, parametric isolation approaches like HPNs (Zhang et al.] 202T) that adaptively select different parameters for different tasks, and memory replay methods like ER-GNN (Zhou & Cao (021) that stores representative nodes. Our work is also based on memory replay and its key advantage lies in being capable of preserving complete topological information with reduced space complexity, which shows significant superiority in class-IL setting (Section 4.4). Note that we study the class-IL for node classification, which is essentially different from the class-IL for graph-level prediction (Carta et al. (02I). Memory replay for graph-level tasks stores individual graphs and will not trigger the memory explosion problem (same as traditional continual learning node classification and aim to resolve the memory explosion problem. problem.Finally. it is worth highlighting the difference between continual graph learning and some relevant but different research areas. First, dynamic graph learning (Galke et al. 22020) Wang et al. 2020cc Han et al.) 2020 Yu et al. 2018 Nguyen et al., 2018 Zhou et al. [0188 Ma et al. 2020; Feng et al., al.] 2020) focuses on the temporal node dynamics with all previous data being accessible. In contrast, continual graph learning aims to alleviate forgetting, therefore the previous data inaccessible. Second, few-shot graph learning (Zhou et al.] 2019) Guo et al.] [02T] Yao et al.] 2020) Tann et al., (222)) targets fast adaptation to new tasks. In training, few-shot learning models can access all previous tasks simultaneously (unavailable in continual learning). For evaluation, few-shot learning models need to be fine-tuned on the new test classes, while the continual learning models are evaluated over existing tasks without fine-tuning.
Euclidean data). In this work, we focus the class- II for
2.2 DECOUPLED GRAPH NEURAL NETWORKS & RESERVOIR COMPUTING
Unlike the early works with interleaved neighborhood aggregation and node feature transforma- tion (Kipf & Welling, 2016: Gilmer et al., 2017; Veličković et al.] 2017 Xu et al.] 2018 Chen
et al. 2018, Hamilton
al. 2017), recent works reveal that decoupling these two operations can reduce complexity and increase scalability, while maintaining equivalent or even achieving superior
performance for GNNs (Zeng et al. [021 Chen et al. 22200] 2019; Ni & Maehara 2019 Frasca et al.) 2020). For instance, Simple Graph Convolution (SGC) (Wu et al. 2019a) removes the non-linear activations from GCN and only keeps one neighborhood aggregation and one node transformation layer. Approximate Personalized Propagation of Neural Predictions (APPNP) (Klicpera et al.) 2018) first performs node transformation and then conducts multiple neighborhood aggregations in one layer. Following these works. works..Dong et al. (202T) prove that the decoupling strategy to predict then propagate is equivalent to training on the unlabelled nodes with pseudo labels aggregated from the labeled neighbors. To further explore decoupled GNNs, [Chen GNNs.Chen et al. (2020) formulate the Braph-Augmente Multi-Layer Perceptrons (GA-MLPs). and theoretically analyzed their expressive power. Instead of decoupling the structures, Zeng al. (202T) propose SHADOW-GNN to decouple the depth and scope of GNNs by fixing the depth of the computation subgraph. Among these works, some can be viewed instantiations of PDGNNs (Wu et al., [2019a] Zhu & Koniusz 2020 Gallicchio & Micheli 2020). while the others may not focus on decoupling the trainable parameters and the space complexity is still ((dd)) when applying memory replay, egg. APPNP (Klicpera et al. 2018
Propagation then Training Adaptively (PTA) (Dong et al. 2021), etc.. Besides works on decoupling GNNs, PDGNNS are also related to reservoir computing based GNNs (Gallicchio & Micheli, 2020 2010h, which embed the graphs via a fixed, non-linear system followed by a trainable linear readout module. The reservoir computing modules can be adopted in PDGNNs as the SSE generation function (Equation 4. and the corresponding experimental results are in Appendix C.5
PARAMETER DECOUPLED GNNS WITH SUFFICIENT SUBGRAPH EMBEDDING MEMORY
In this section, we first introduce the notations and then explain the technical challenge of applying memory replay techniques to GNNs. Targeting the challenge, introduce PDGNNs with Sufficient Subgraph Embedding Memory (SSEM). Finally, inspired by theoretical findings of the pseduo- training effect, we develop the coverage maximization sampling. It can empirically improve the continual learning performance, especially when the memory budget is tight. All detailed proofs are provided in the Appendix B
3

---

Under review as a conference paper at ICLR 2023
3.1 PRELIMINARIES
In this paper, continual graph learning is formulated as learning node representations on a sequence of subgraphs (tasks): = 1 G2. ..., Gr). Each subgraph 9, contains several new emerging categories of nodes in the overall graph and is associated with a node set V,, and an edge set E,, which is represented as the adjacency matrix A, RVV./xIV.] Each entry of A, denotes an edge between pair of nodes. The degree of node d refers to the number of edges connected to it. practice, A, is
often normalized as A, -D, AD where D,- R|V+IXIV+ is the degree matrix. Each node v E V- has a feature vector X. E R. In classification tasks, each node v has a label yv E {0, 1JC; where C' is the total number of classes. When generating the representation for a target node v. GNNs typically take a subgraph within Gr as the input, which is denoted as the computation subgraph g For simplicity, 9odd may be used in the following, without the graph index. We define the L-hop neighbors of a node as N (v) which contains all nodes within a distance of L from v.
3.2 MEMORY REPLAY MEETS GNNS
In traditional continual learning. model f(-: θ) parameterized by @ is trained on a sequence of T tasks. Each task (T E {I...., T)) corresponds to a dataset Dr, {(x, ) To avoid forgetting, memory replay based methods store representative data from the old tasks in buffer B, which are replayed when learning new tasks. A common approach to utilize B is through an auxiliary loss:
== Σ (f(xx;0))xr) +A X;ED,
Σ EB
(f(xx;0).x))
Cy: loss of the current task
Loux! auxiliary loss
where I(:,)) denotes the loss function, and À 2 balances the contribution of the old data. The buffer B may also be used in other ways to prevent forgetting instead of directly minimizing Lauz Lopez-Paz & Ranzato (2017); Rebulfi al. (017). In these applications, the space complexity of
buffer containing n examples is O()).
However, to capture the topological information, GNNs obtain the representation of a node based on computation subgraph surrounding v. We exemplify it with the popular MPNN framework (Gimer et al. 2017), which updates the hidden node representations at the + 1-th layer as:
m
(+1
Σ (v)
Mi(h h ww
[+1 = U2(h', m 1+1 ,
(2)
where h², h are hidden representations of nodes at layer 1, _ is the edge feature, M, OM) is the message function to integrate neighborhood information, and U updates m into hy, When I = hς denotes the input node features. In I--layer MPNN, the representation of node e can be simplified as,
h = MPNN(Xx Goub, uaub θ),
(3)
where geab is the computation subgraph containing the I.-hop neighbors (i.e., (v)).. (PNN(; O) the composition of all M,(... OM)) and U at different layers. Since (u) typically contains (dd)) nodes, replaying n sampled nodes would require storing O(nd") nodes (the edges of Gaub are not counted yet), where d is the average node degree. Take the Reddit dataset (Hamilton et al. 2017) as concrete example, its average degree is 492, even with a layer MPNN, the buffer size will be easily intractable. Therefore, directly storing the computation subgraphs for memory replay is infeasible for GNNs. Besides, the unsupervised lcarning models Ad hikari al. 2018); Narayanan al. 2016) also suffer from this problem. Because the trainable parameters in the unsupervised learning part will also be updated after learning each task, the original computation subgraphs are required for retraining the model.
3.3 PARAMETER DECOUPLED GNNS WITH SSEM
As we discussed earlier, the key difficulty of applying memory replay to graph data is to store the computation subgraphs with potentially unbounded sizes. Therefore, we would naturally expect to preserve the necessary information (e.g., the topological information) of computation subgraph with a vector of fixed length such that the memory consumption can be manageable. Formally, the desired subgraph representation can be defined as Sufficient Subgraph Embedding (SSE).
Definition 1 (Sufficient subgraph embedding). Given model parameterized with o and an input Gauh, an embedding vector e, is sufficient subgraph embedding for gsmh uh if optimizing 0 with G or By equivalent.
4

---

Under review as a conference paper at ICLR 2023
Given the definition, aim to derive SSEs from the computation subgraphs. As have shown in Section 3.2, SSEs cannot be derived from the MPNNs due to their interleaved neighborhood aggrega- tion and feature transformations, i.e., whenever the trainable parameters get updated, recalculating the representation of u requires all nodes and edges of Gzub. To resolve this issue, we formulate the Parameter Decoupled Graph Neural Networks (PDGNNs) framework, which decouples the trainable parameters from the individual nodes/edges. PDGNNs may not be the only feasible framework to derive SSEs, but is the first attempt in this direction and is empirically verified to be effective. Given a computation subgraph gedd, the prediction of node with PDGNNs consists of two steps. First, the topological information of 9 is encoded into an embedding e, via the function f-opo()) without trainable parameters (instantiations of (eopo( are detailed in Section 3.4
ey foopo (g
Next, e, is further passed into trainable function (-: parametrized by 0 (instantiations of (: 0) are detailed in Section 3.4) h to get the output prediction 8v.
y. = fout 0).
With the formulations above, e, derived in Eq. 4 clearly satisfies the requirements of SSE (Defini- tion D. Specifically, since the trainable parameters acts on c2 instead of directly on any individual node/edge, optimizing the model parameters with either e, or g are equivalent.
Since SSEs are equivalent to the computation subgraphs for optimizing PDGNNs, the memory buffer only needs to store SSEs to reduce the space complexity from (ndd²) to (n)). For convenience, we refer to Gaué as the computation subgraph of both and e We name the buffer to store the SSEs as Sufficient Subgraph Embedding Memory (SSEM). Given a new task т, the update of SSEM is:
(6) where sampler(..-) denotes the adopted sampling strategy to populate the buffer, V denotes the set union, and n is the budget size. As long as a memory buffer SSEM is maintained, our PDGNNs- SSEM perform well with different sampling strategies including random sampling. But in Section 3.6. based on the theoretical insights in Section 3.5] we propose a special sampling strategy to better populate SSEM, which is empirically verified to be beneficial when the memory budget is tight. Equation (6) assumes a scenario where all data of the current task are presented concurrently. In practice, if the data of a task are presented in multiple batches (e.g., nodes come in batches on large graphs), the buffer update can be modified by adopting mechanisms to replace the existing data, which is detailed in Appendix A
SSEM = SSEM U sampler(fe,,
v)).n),
For task T with graph Gr, the loss with SSEM then becomes:
L =
Σ (Co) v)) VEV,
Σ
I(four(Cw: Vw),
CLESSSM
Cy: loss of the current task T
Lauzi muxiliary loss
where the e, the current task is calculated according to Equation (8). Different from traditional continual learning works which choose X manually, on graph data, we re-scale the losses according to the class sizes counter the bias from the severe class imbalance, which cannot be handled on graphs by directly balancing the datasets (details are provided in Appendix C.2).
3.4 INSTANTIATIONS OF PDGNNS
Although without trainable parameters, the function (.opo(.) for generating SSEs can be highly expressive with various formulations including linear and non-linear ones, both of which are studied in this work. We will mainly focus on the linear formulations, which are empirically comparable to the non-linear choices (Appendix C.3) but is much more efficient and convenient for theoretical analysis (Section 3.5 and 3.6) The linear instantiations of f-opo(-) can be generally formulated as,
eg = koopo (G.ub)
X TV, w:; A):
WEY
where ... A) denotes the adopted strategy for computation subgraph construction based on the structure A (the normalized adjacency matrix defined in Section 3.1).
Next, to instantiate T.. A), we first formulate the SSE generation for all nodes in V as a matrix multiplication: Ey = IIX,, where each entry II,, = π w; A). Ey E RVVx is the concate- nation of all SSEs (e, E 18²), and X E glVxxb is the concatenation of all node feature vectors x, E R
The following three options are adopted as instantiations of II in our experiments:
1. SGC Wu et al. (0019)): II - A
2. S2G Zhu & Koniusz (2020): II I EL ((1 A' +al)
5

---

Under review as a conference paper at ICLR 2023
3. APPNP Klicpera et al.
20188: II ((1
Note that PDGNNs is general framework, and some existing decoupled GNNs are instantiations of PDGNNs, e.g., SGC [W ct al.
(019a) and S²GC ZZhu & Koniusz (2020). However, the other decoupled GNNs may not decouple the trainable parameters from individual nodes, and the space complexity is still (ndd when applying memory replay, e.g. APPNP Klicpera et al. (2018), PTA
Dong et al. 2021.. etc..
The linear formulation of (.apo(.) described above in Equation 8 could yield both promising experi- mental results (Section C) and instructive theoretical results (Section [.5 and (3.6). Equation X is also highly efficient especially for large graphs due to the absence of iterative neighborhood aggregations. Besides, (.) can also take non-linear forms with more complex mappings, e.g., the reservoir computing modules Gallicchio & Micheli (2020). The corresponding experimental and theoretical effects are introduced in Appendix (B.3 and C.5).
Since the function four (:; 0) simply deals with individual vectors (SSEs), it is instantiated MLP in this work. The specific contigurations of foue(+ 0) is described in the experimental part (Section 4.2)
3.5 PSEUDO-TRAINING EFFECTS OF SSES In traditional continual learning on Euclidean data without topological connections, replaying an example x; (e.g., an image) only reinforces the prediction of x; itself. In this subsection, we introduce the pscudo-training effect of SSEs, which implies that training PDGNNs with e of node e also influences the predictions of the other nodes in Gomh, based on which we develop novel sampling strategy to further boost the continual learning performance on graphs.
Figure 2: Illustration of the coverage ratio. Sup- posing the graph has N nodes in total, Ro(fu}) = N. (c(())
13
N Re((u]) = and
Ro((u, U, w)) = 42 N
Theorem 1 (Pseudo-training). Given a node v, its computation subgraph Goub, the SSE e, and label yo (suppose e belongs to class k. i.e. Yo,k = =1,, then training PDGNNs with e, has the following two properties:
1. It is equivalent to training PDGNNs with each node in Goub with Goub being a pseudo computation subgraph and y. being a pseudo label, where the contribution of Xw (via Equation 8 re-scaled by s(v.w:A). a(w,w:A) We term this property as the pseudo-training effect on neighboring nodes, because is equivalent to that the training is conducted on each neighboring node (in goud) through the pseudo labels and the pseudo compulation subgraphs.
When (o 0) is linear, training PDGNNs on e, is also equivalent to training (: 0) on pseudo- labeled nodes (Xw: yv) for each in Goub, where the contribution of w in the loss is adaptively re-scaled with weight
Fxue(X (0) (V)
Σ Engrgah fort X ((0.:AA):))
The pseudo-training effect essentially arises from the neighborhood aggregation operation. Due the prevalence of homophily (defined in Appendix(B3. B.2) in real-world graphs, neighborhood aggregation (i.e., message passing) is widely adopted in mainstream GNNs to enhance the performance by encouraging similar representations and predictions for neighbored nodes. Similarly, pseudo-training effect implics that replaying the SSE of a buffered node is encouraging a similar prediction for its neighbors (not buffered), which is also beneficial on homophilous graphs. In other words, the homophilous neighbors of a buffered node u do not need to be stored, but the forgetting problem on them can also be alleviated by replaying the SSE of Besides, when (: 0) is linear, the re- re-scaling weight in Theorem 2 can adjust the pseudo-training on neighboring nodes according to their homophily to some extent. Specifically, larger forr (x 0) denotes a higher confidence to classify w into class k. and higher T (V. w; A) typically denotes higher similarity between w and v. Therefore, the pseudo- teadoottaiiing is stronger on the homophilous neighbors (with same labels) and weaker on the heterophilous neighbors (with different labels), according to the prediction confidence of foue(:: 0). Note that although homophily brings this extra benefit, it is not prerequisite for our model to work. Despite the homophily, replaying e, still reinforces the prediction of node v itself, just like memory replay in traditional continual learning independent data (e.g., images). However, real-world graphs often exhibit strong homophily, and pseudo-training effect is generally beneficial, which is also empirically justified (Section 4.3)

---

Under review as a conference paper at ICLR 2023
Table 1: The detailed statistics of datasets and task splittings
Dataset
CoraFull
McCallum Morallll/MCalllm
al. 2000
OGB-Arxi
RoddinHamilton Hamilton al. 2017
OGB-Product 0
# nodes
19,793
169,343
232,965
2,449,029
# edges
130,622
1,160,243
114,615,892
61,859,140
# classes
70
40
47
# tasks
30 / 14/5/2
20/ 8/2/2
20 5//2
23 / 10//5/3 1/3
The above analysis suggests that SSEs with larger computation graphs covering more nodes may be more effective. the next subsection, we design the coverage maximization sampling strategy to leverage the benefit of the pseudo-training effect.
3.6 COVERAGE MAXIMIZATION SAMPLING
Algorithm 1 Coverage maximization sampling
Following the ahove subsection, quantify the number of nodes covered by the selected SSEs versus the total number of nodes in the graph, we define the coverage ratio of the SSEs. In the following, since each SSE uniquely corre- sponds to node, we may use 'node' and 'SSE' interchangeably
Input: G. V.. A., π(. :-), sample size n. Output: Selected nodes 8
1: Initialize S = (.
2: for each V de
3: (c((v)) = Hw w
19,1
4: end for each
5: for each v V do
Definition 2. Given a graph G, node set V, and function T A), the coverage rutio of a set of nodes V, is:
6: P. = Eucr, R.11w]]
Reltes)
7: end for each
8: while > do
Re(V.)= Uoev, {wiww E Goub)
Sample one node v from V, according to (pw)
w E V.
[V]
10:
S = S [e]
Le., the ratio of nodes of the entire (training)
11:
V, = V, Hujo Sampling without replacement
graph covered by the computation subgraphs of the selected nodes (SSEs).
12:
n + n
13:
end while
To maximize (sSESMM) naive approach is to start from the SSE with the largest coverage ratio and iteratively incorporate SSE that increases Rc(SSEM) the most. However, this requires computing (SSEMM for all possible SSEs in each iteration, which is time consuming especially on large graphs. Besides, certain randomness is also desired for the diversity of SSEM. Therefore, we propose to sample SSEs from a multinomial distribution based on the coverage ratio of each individual SSE. Specifically, in task T with node set V,, the probability of sampling node v E V, is Pe Ewev, Re((w:)) Then the procedure is to sample from V, according to {pe V,) without replacement, as shown in Algorithm [ In experiments, we compare different sampling strategies to demonstrate the strong correlation between the coverage ratio and the performance, which also verifies the benefits revealed in Section 3.5
Re((=])
EXPERIMENTS
In this section, we aim to answer the following questions: QI: Whether PDGNNs-SSEM work well with a reasonable buffer size? Q2: Does coverage maximization sampling ensure higher coverage ratio? Q3: Whether our theoretical results can be empirically justified? Q4: Does higher coverage ratio lead to better performance? Q5: Whether PDGNNs- SSEM can outperform the state-of-the-an methods in both class- II. and task-ll. scenarios? Due to the space limitations, only the most prominent results are presented in the main content, and more details are available in Appendix. For simplicity, EDGNNs-SSEN, will be denoted as PDGNNs in this section.
4.1 DATASETS
We adopted four public datasets, CoraFull, AGB-Arxiv, Reddit, and NGB-Products, with up to millions of nodes and 70 classes. Dataset statisties and task splittings (i.e., how partition the node classes into different tasks) are summarized in Table In the paper, we show the results under the splittings with the largest number of tasks. More details of the datasets, dataset splittings, and the results with other task splittings are provided in the Appendix C.I C.2 C.4
4.2 EXPERIMENTAL SETUP AND MODEL EVALUATION
Continual learning setting and model evaluation. During training. a model is trained task sequence with access only to the subgraphs of the current task. After that, the model is tested on all learned tasks. In the class-IL scenario, model has classify a given node by picking class from all learned classes (which is more challenging), while the task-IL scenario only requires the model
7

---

Under review as a conference paper at ICLR 2023
Table Performance & coverage ratios difffrent sampling strategies and buffer sizes on OGB-Arxiv dataset (1 higher means better).
Ratio of dataset/ 1%
0.02
0.1
1.0
5.0
40.0
Uniform samp.
12.0:1.11
2..11:1.7
42.2:10.3
5041004
53.3.10.4
AA %
Mean of feat.
12.6:20.1
25,3:0033
42.8+-033
50.40.77
53.3::0.2
Max.
1..9=008
2681:8
43.7:0.5
50.5=0.4
53,4:0.11
Unitorm samp.
0.1=0.11
0.3:2000
3.5=099
15.94111
84.8:11555
Cov. ratio/S
Mean of feat.
0.2
0.6.10.3
7.1
2,761:17
91.110.1
Cov, Max.
0,5
1.9
1.6
46.3-10.6
92.8:10.0
Table 3: Performance comparisons under class IL on different datasets (1 higher means better).
CoraFull
OGB-Ard Arsiv
Reddit
OGB Products
C.I.T.
AA7% 7
AF%
AA/%
AF7
AA 1
AF7 1
AA%% 1
AF7% 1
Fine-tune
3,5+0.2
-5..2+0.33
49400
-89.740044
5.940.9
.97.9
7.6+0.66
-88.7-00.5
EWC 2017
52.645.0
-3,5577.3
8.5+066
-69.5+44.7
10.3+6.33
-33.2=14.6
23.8+2.2
-21.743.9
MAS
2013
6.5+1110
42.3+110
4.8+002
-72.242266
9.247766
12.11=14.6
16.74:2.
-57.0=24.8
GEM
2017
7,40.11
-91.000.1
494000
-89.8+02
5.0=0..0
-9..4:0.0
4.5+0.8
-94.740.2
TWP
6..6::1
-3.6:288
6.7112
-0.61699
8.0:2.99
-188:5.1
14.1+22.1
-11.4:1:33
LwF 2017
33.4:10.9
19.6.1.2
9.9.6.77
43.6.7.55
86.6.10.88
9.2.
48.2.10.8
-18.6.1099
GNN
2.9.0.0
94.6.0..1
12.12311
-79.943.3
20.44:..66
-82.7429
56.74:0.3
-33.340.55
Joint
80.8:0.11
-3.1:0.2
56.8=0.00
-8.6=0.00
97.1+0.11
-0.7-0.1
71.5+0.1
-58820.2
PDGNNs 81.9.0.1
3.9.1.111
5..2:002
.1.77.0.22
96.6.100.0
2.66
73.910.1
10.9:10.22
to distinguish the classes within each task. For model evaluation, the most thorough metric is the accuracy matrix M E RRTx,, where M denotes the accuracy task after learning task i. The
learning dynamics are shown with the curves of average accuracy (AA): |-:=
M
1, I,..,, T
and the average forgetting (AF): { varies. To use single numeric value for evaluation, the AA and AF after learning all T tasks will be used. We repeat all experiments 5 times on one Nvidia Titan Xp GPU. All results are reported with average performance and standard deviations.
2, ...,, T) when the number of learned tasks
Baselines and model settings. Our baselines include the methods designed for continual graph learning including Experience Replay based GNN (ERGNN) (Zhou & Cao (021) and Topology- aware Weight Preserving (TWP) (Liu et al. 2021). and milestone works designed for Euclidean data but also applicable to GNNs including Elastic Weight Consolidation (EWC) (Kirkpatrick et al. (017).
Learning without Forgetting (LwF) (Li & Hoiem 2017). Gradient Episodic Memory (GEM) (Lopez)
Paz & Ranzato 2017), and Memory Aware Synapses (MAS) (Aljundi al. 2018). ). These baselines
are implemented based on three popular backbone GNNs, i.e., Graph Convolutional Networks (GCNs)
(Kipf & Welling 2016). Graph Attentional Networks (GATs) (Veličković al.. [2077). and Graph
Isomorphism Network (GIN) (Xu et al.) 2018). Besides, joint training (without forgetting problem) and fine-tune (without continual learning technique) are adopted as the upper and lower bound for performance comparison. We instantiate (-ue(:; 0) as a multi-layer perceptron (MIP). To make fair comparison, all methods including f-ue(:; 0) of PDGNNs are set as 2-layer with 256 hidden dimensions, and the neighborhood aggregation range of PDGNNs (L in Section 3.3) is also set as 2 for consistency. As detailed in Section 4.3 f.opo(.) is chosen as the SGC strategy (Section 3.4. while the comparison among different choices is introduced in Appendix C.4
4.3 STUDIES ON THE BUFFER SIZE & PERFORMANCE vs. COVERAGE RATIO (Q1,2,3,4)
In Table 2 based on PDGNNs, we compare the proposed coverage maximization sampling with uniform sampling and mean of feature (MoF) in terms of coverage ratios and performance when the buffer size (ratio of dataset) varies from 0.0002 to 0.4 on OGB-Arxiv. More complicated sampling methods Hübler al. (2008); Yang al. (0066) can also be used. However, the sampling methods adopted in this work can already obtain performance comparable to Joint, and are highly efficient. The proposed coverage maximization sampling achieves a superior coverage ratio, especially when buffer sizes are relatively small. We also notice that the average accuracy for coverage maximization sampling is positively related to the coverage ratio in general, which verifies Theorem Table 2 also shows the positive correlation between the buffer size and the performance. Besides, our SSEM appears to be highly efficient in terms of memory usage. No matter which sampling strategy is used, the performance In Appendix C..), we further evaluate how the performance changes when the buffer size varies with different variants of PDGNNs (Le., the SSE generation strategies adopted from SGC, SCG APPNP,
reach =50 average accuracy (AA) with only 5% data buffered.
8

---

Under review as a conference paper at ICLR 2023
Average accuracy
100
Averaige accuracy 8
Average accuracy
Average eccuracy
100
Ey GNN
8 8 8 80
Fim SuTM
60
GEM
40
Lef
20
POGNNS
John
Figure 3: Dynamics of average accuracy in class-IL scenario. From left to right: OGB-Arxiv, classes per
task. 2. CoraFull, 2 classes per task. 3. Reddit, 2 classes per task. 4. CGB-Products, classes per task.
11
10
Tocks
10
Tasks
10
Tasks
10
50
15
15
15
10
20
10
15
20
Tasks
Tasks
Tasks
Tasks
Figure 4: From left to right: accuracy matrix of PDGNNs, ER-GNN, LwF, and Fine-tune on OGB-Arxin dataset.
Table 4: Performance comparisons under task- on different datasets (t higher means better).
CoraFull
OGB-ArXiv
Reddit
OGB-Products AF
C.L.T.
AA/% f
AB%
AA/%
AF 1%
AA% f
AF/% /%
AA/%
Fine-tune
26.0++2.4
-1.0=2255
56.2+177
136.2
79.5+13.0
-11.729
64.442233
-31.1+22.6
EWC 2017
89.810.77
0,3
11.4
-0.1044
83991119
-2.01:10
87.01009
-1.7:1099
92.240.6
.37....8
7..711.6
11.5511.66
61.114.3
-0..10.7
8066124
-13.71:24
GEM
2017
92.0++0.4
0.3+0088
8088-088
-5.34099
98.9=0.0
-0.5+0.11
87.7+111
-7.0=1.22
TWP
2021
94.3+005
-1.6+0.3
80.9=100
-1330088
78.02:33.4
-0.2::0.3
8188222
-0.3-0.55
I.
2017
93.840.1
-0420.11
71.1
-1.500
98.610.1
-0.0::0.0
863110.1
10.50.11
ER-GNN
22221
62.4+155
13,.5=1.5
86.420.2
0,5=0.3
97.5+1.5
2.6
86.4000
11.7=00
Joint
96.0+1:.1
0.0:0..1
90.3:002
0.5
99.5::0.0
0,0:0.00
95.34.0.4
-0.3+0.33
PDGNNs
94.6
0.6:1
89.8=00.4
-0.0+:0.5
98.9:20.0
-0.5+0.00
93.5+0.5
-2.1
and reservoir computing described in Section 3.3
The SGC strategy is more efficient than the other variants with comparable performance, therefore is chosen in our following experiments.
4.4 RESULTS FOR CLASS-IL SCENARIO AND TASK-IL SCENARIO (Q5)
Class-IL Scenario. We compare PDGNNs with the baselines on 4 public datasets under the class- IL scenario. As shown in Table 3 PDGNNs significantly outperform the baselines and is even comparable to joint training (the performance upper bound) on 4 different datasets. The learning dynamics are also shown in Figure Among the baselines, those techniques relying on regularization or Fine-tune exhibit severe forgetting problems. LwF performs slightly better than them since knowledge distillation employed. ER-GNN outperforms LwF since leverages memory replay to maintain performance over old tasks. For clarity, we omit the error bars on the CoraFull dataset. Full results with error bars are available in Appendix C.4
To further understand the dynamics of different methods under the class-IL scenario, we visualize the accuracy matrices of PDGNNs, ER- ER-GNN, LwF, and Fine-tune in Figure 4 Each row of the matrix denotes the performance on all tasks after learning new task, and each column denotes the performance change of a specific task when learning all tasks sequentially. Compared to baselines exhibiting severer forgetting when learning new tasks, PDGNNS can maintain relatively stable performance on each task even though new tasks are continuously learned. Besides, we also visualized the learnt node representations of after learning all tasks, which is shown in Appendix CC.4 Task-IL Scenario. In Table 4 we can observe that PDGNNs still outperform baselines on all 4 different datasets under the task-IL scenario even though is less challenging than the class- IL scenario we discussed in Section 2.2, Due to space limitations, more detailed discussions about the results and the learning dynamics with the task-ll. scenario are provided in Appendix C.4
5 CONCLUSION
In this work, we propose the PDGNNs with SSEM for continual graph representation learning. Based on SSEs, we reduce the memory space complexity from O(nd)) to (n). which enables PDGNNs to fully utilize the explicit topological information sampled from previous tasks. We also discover and theoretically analyze the sgeudo-training effect of SSEs. This inspires us to develop coverage maximization sampling which has been demonstrated to be highly efficient especially when the memory budget is tight. Finally, thorough empirical studies on both class-IL IL and task-IL continual learning scenarios demonstrate the effectiveness of PDGNNs-SSEM.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Bijaya Adhikari, Yao Zhang, Naren Ramakrishnan, and B Aditya Prakash. Sub2vec: Feature learning for subgraphs. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 170-182. Springer, 2018.
Rahaf Aljundi, Francesca Babiloni, Mohamed Elhoseiny, Marcus Rohrbach, and Tinne Tuytelaars. Memory aware synapses: Learning what (not) to forget. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 139 154, 2018.
Rahaf Aljundi, Min Lin, Baptiste Goujaud, and Yoshua Bengio. Gradient based sample selection for online continual learning, Advances in Neural Information Processing Systems, pp. 11816- 11825, 2019.
Lucas Caccia, Eugene Belilovsky, Massimo Caccia, and Joelle Pineau. Online learned continual com- pression with adaptive quantization modules. In International Conference on Machine Learming, pp. 1240-1250. PMLR, 2020.
Antonio Carta, Andrea Cossu, Federico Errica, and Davide Bacciu. Catastrophic forgetting in deep graph networks: an introductory benchmark for graph classification. arXiv preprint 1rXiv:2103.11750 2021.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. arXiv preprint arXiv: 10568, 2017.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint
2018.
Lei Chen, Zhengdao Chen, and Joan Bruna. On graph neural networks versus graph-augmented mlps. arXiv preprint 11112000111116.. 2020.
Ting Chen, Song Bian, and Yizhou Sun. Are powerful graph neural nets necessary? a dissection on graph classification. arXiv preprint arXiv: 0ttl:/9905.0455 04579, 2019.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 257-266, 2019.
Aristotelis Chrysakis and Marie-Francine Moens. Online continual learning from imbalanced data. In International Conference on Machine Learning, pp. 1952-1961. PMLR, 2020.
Angel Daruna, Mehul Gupta, Mohan Sridharan, and Sonia Chernova. Continual learning of knowledge graph embeddings. IEEE Robotics and Automation Letters, 6(2): 1228-111111 11111121115555 1135, 2021.
Hande Dong, Jiawei Chen, Fuli Feng, Xiangnan Hc, Shuxian Bi, Zhaolin Ding, and Peng Cui. On the equivalence of decoupled graph convolution network and label propagation. In Proceedings of the Web Conference 202/, pp. 3651-3662, 2021.
Mchrdad Farajtabar, Navid Azizan, Alex Mott, and Ang Li. Orthogonal gradient descent for continual learning. In International Conference on Artificial Intelligence and Statistics, pp. 3762-3773. PMLR, 2020.
Yutong Feng, Jianwen Jiang, and Yue Gao. Incremental learning on growing graphs. 2020.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.111 21000004..1....... 2020.
Lukas Galke, lacopo Vagliano, and Ansgar Scherp. Incremental training of graph neural networks on temporal graphs under distribution shift. arXiv preprint arXiv:2006.144 14422, 2020.
Claudio Gallicchio and Alessio Micheli. Graph echo state networks. In The 2010 international joint conference on neural networks (IJCNN), pp. 1-8. IEEE, 2010.
10

---

Under review as a conference paper at ICLR 2023
Claudio Gallicchio and Alessio Micheli. Fast and deep graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 3898-388833 -908,,99,,00 2020.
Spyros Gidaris and Nikos Komodakis. Dynamic few-shot visual learning without forgetting. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4367-4375, 2018.
Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry, In International Conference on Machine Learning, Pp. 1263 1272. PMLR, 2017.
Zhichun Guo, Chuxu Zhang, Wenhao Yu, John Herr, Olaf Wiest, Meng Jiang, and Nitesh Chawla. Few-shot graph learning for molecular property prediction. In Proceedings of the Web Conference 2021, pp. 2559-2567, 2021.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs In Advances in Neural Information Processing Systems. pp. 1024-1034, 2017.
Yi Han, Shanika Karunasekera, and Christopher Leckie. Graph neural networks with continual learning for fake news detection from social media. arXiv preprint arXiv:2007.03316, 2020.
Tyler Hayes and Christopher Kanan. Lifelong machine learning with deep streaming linear discriminant analysis. Proceedings the IEEE/CVF conference on computer vision and pattern recognition workshops, pp. 220-221, 2020.
Christian Hübler, Hans-Peter Kriegel, Karsten Borgwardt, and Zoubin Ghahramani. Metropolis algorithms for representative subgraph sampling. In 2008 Eighth IEEE International Conference Data Mining, pp. 283-2883 292. IEEE, 2008
Thomas Kipf and Max Welling. Semi- supervuper classification with graph convolutional networks. 2016.
arXiv preprint
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinse Barwinskw, et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences, 114 (13):3521-3526 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint 11X1v:1810.05997, 2018.
Zhizhong Li and Derek Hoiem. Learning without forgetting. IEEE Transactions Pattern Analysis and Machine Intelligence, 40 40(12):2935-2947, 2017.
Huihui Liu, Yiding Yang, and Xinchao Wang. Overcoming catastrophic forgetting in graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 8653-8661,
David Lopez-Paz and Mare' Aurelio Ranzato. Gradient episodic memory for continual learning. In Advances in Neural Information Processing Systems, pp. 6467-6476, 2017.
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, pp. 719-728, 2020.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? arXiv preprint 106iv:2/06.06/:: 2021.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
Annamalai Narayanan, Mahinthan Chandramohan, Lihui Chen, Yang Liu, and Santhoshkumar Saminathan. subgraph2vec: Learning distributed representations of rooted sub-graphs from large graphs. arXiv preprint arXiv: 1606.0890 2016.

---

Under review as a conference paper at ICLR 2023
Giang Hoang Nguyen, John Boaz Lee, Ryan A Rossi, Nesreen K Ahmed, Eunyee Koh, and Sungchul Kim. Continuous time dynamic network embeddings. In Companion Proceedings of the The Web Conference 2018, pp. 969-976, 2018.
Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All have is low-pass filters. arXiv preprini arXiv: 09550, 2019.
SyllestreeAAlvse Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampert. icarl: Incremental classifier and representation learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2001-2016 2017.
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: 04671, 2016.
Hanul Shin, Jung Kwon Lee, Jaehong Kim, and Jiwon Kim. Continual learning with deep generative replay. In Advances in Neural Information Processing Systems, pp. 2990-2999, 2017.
Zhen Tan, Kaize Ding. Ruocheng Guo, and Huan Liu. Graph few-shot class incremenntt learning, In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pp- 987-996, 2022.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Rexearch, 9(11), 2008
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
Chen Wang, Yuheng Qiu, and Sebastian Scherer. Bridging graph network to lifelong learning with feature interaction. 2020a.
Chen Wang, Yuheng Qiu, and Sebastian Scherer. Lifelong graph learning. arXiv preprint arXiv:2009.0063 2020h.
Hao Wang, Yitong Wang, Zheng Zhou, Xing Ji, Dihong Gong, Jingchao Zhou, Zhifeng Li, and Wei Liu. Cosface: Large margin cosine loss for deep face recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5265-5274, 2018.
Junshan Wang, Guojie Song, Yi Wu, and Liang Wang. Streaming graph neural networks via continual learning. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 1515-1524, 2020c.
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1): 396 493, 2020d.
Mitchell Wortsman, Vivek Ramanujan, Rosanne Liu, Aniruddha Kembhavi, Mohammad Rastegari, Jason Yosinski, and Ali Farhadi. Supermasks in superposition. arXiv preprint arXiv:2006. 14769, 2020.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International Conference on Machine Learning, pp. 6861-6871. PMLR, 2019a.
Guile Wu, Shaogang Gong, and Pan Li. Striking balance between stability and plasticity for class- incremental learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1124-118 1133, 2021.
Yue Wu, Yinpeng Chen, Lijuan Wang, Yuancheng Ye, Zicheng Liu, Yandong Guo, and Yun Fu. Large scale incremental learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 374-382, 2019b.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural 2018.
networks? arXiv preprint
12

---

Under review as a conference paper at ICLR 2023
Yishi Xu, Yingxue Zhang, Wei Guo, Huifeng Guo, Ruiming Tang, and Mark Coates. Graphsail:
Graph structure aware incremental learning for recommender systems. In Proceedings of the 29th ACM International Conference Information & Knowledge Management, pp. 2861-2863 2020.
Zhengwei Yang, Ada Wai-Chee Fu, and Ruifeng Liu. Diversified top-k subgraph querying in large graph. In Proceedings of the 2016 International Conference on Management of Data, pp. 1167-1182, 2016.
Huaxiu Yao, Chuxu Zhang, Ying Wei, Meng Jiang, Suhang Wang, Junzhou Huang, Nitesh Chawla, and Zhenhui Li. Graph few-shot learning via knowledge transfer. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 6656-6663, 2020.
Jaehong Yoon, Eunho Yang. Jeongtae Lee, and Sung Ju Hwang. Lifelong learning with dynamically 2017.
expandable networks. arXiv preprint arXiv:
Jachong Yoon, Sachoon Kim, Eunho Yang, and Sung Ju Hwang. Scalable and order-robust contin- ual learning with additive parameter decomposition. In International Conference on Learning Representation, 2020.
Wenchao Yu, Wei Cheng, Charu C Aggarwal, Kai Zhang, Haifeng Chen, and Wei Wang. Netwalk: flexible deep embedding approach for anomaly detection in dynamic networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp- 2018
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
Xikun Zhang, Dongjin Song, and Dacheng Tao. Hierarchical prototype networks for continual graph representation learning. arXiv preprini arXiv:2111.15422, 2021.
Fan Zhou and Chengtai Cao. Overcoming catastrophic forgetting in graph neural networks with experience replay. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 4724 2021.
Fan Zhou, Chengtai Cao, Kunpeng Zhang, Goce Trajcevski, Ting Zhong, and Ji Geng. Meta-gnn: On few-shot node classification in graph meta-learning In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 2357-2360, 2019.
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
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. International Conference on Learning Representations, 2020.
13

---

Under review as a conference paper at ICLR 2023
A ADDITIONAL DETAILS ON PARAMETER DECOUPLED GNNS WITH SSEM
As mentioned in Section 3.3 of the paper, in real-world applications, the data may come in batches instead being presented simultaneously. Therefore, the updating of SSEM may need modification. The key issue is to determine how to update SSEM such that the newly sampled SSEs can be accommodated accordingly. We present two different approaches handle this.
1.
The most straightforward approach is to store the computation subgraph size s5th of each e, and recalculate the multinomial distribution. Given the incoming new node set v, the probability of sampling each node recalculated as p. WEY, USSEM
SaME- Then n. SSEs
are sampled populate the SSEM.
2. For efficiency, can also adopt the reservoir sampling based strategy update existing SSEs in S without recalculating the multinomial distribution. Specifically, given a new node set V,, we first sample min [ |) nodes (SSEs) S from V, with the coverage maximization sampling. Next, we align all SSEs in SSEM and S in a sequence, i.e. the first |SSEM| elements are from SSEM and the following elements are from S. Finally. for each SSE C₂ in S, suppose its order in the sequence is or E {|SSEM], |SSEM] 1, 1,.... (SEEM + [S]], we generate a random integer r from uniform distribution on to SSEEM + o. If falls in the range from to |SSEM], then the r-th SSEs in SSEM is replaced by e.. otherwise e, is deleted. In this way, the nodes in SSEM can be randomly
updated with the newly sampled SSEs.
B THEORETICAL ANALYSIS
In this section, we give proofs and detailed analysis of the theoretical results in the paper.
B. PARAMETER DECOUPLED GNNS WITH SSEM
we mentioned that the embedding e, derived in PDGNNs is sufficient subgraph embedding of Goub with respect to the optimization of 0, Although this straightforward, we still provide a proof for completeness.
In Section 3.3
Proof. According to Definition I a sufficient condition for vector to be a sufficient subgraph embedding of Grub is that e provides same information as Goub for optimizing the parameter 0 of model (-; 0). Therefore, the proof can be done by showing VoL(e,. 0) = VoL(g 0). where the adopted loss function. This becomes straightforward under the PDGNNs framework since Geab is first embedded in e, and then participate in the computation with the trainable parameter 0. Specifically, given an input computation subgraph Grab with the label yus the corresponding prediction of PDGNNs is:
foud
Σ WVVa
X T(, ((, A): 0).
(10)
and the loss is:
Lu =1 fout Σ X (,,, -))
(11)
WEVaub
the gradient of loss Cy is:
VoL, = Vol fout
Σ X T(o, A);
(12)
WE Staub
When the input G:ub is replaced with e. the prediction becomes:
y. (oue(Co; 0),
(13)
14

---

Under review as a conference paper at ICLR 2023
and the corresponding loss becomes:
C = (fou(((eev::)
(14)
the gradient of loss Lu becomes:
VoL.
(15)
Since in the PDGNNs, e, calculated as:
e,
Σ
Xw ((U, w; A),
(16)
WEVaus
then we have:
VoL. = VoL
(17)
ie., optimizing the trainable parameters with e, is equal optimizing the trainable parameters with goub.
B.2 PSEUDO-TRAINING EFFECTS OF SSES
Theorem 1 (Pseudo-training: Given a node u. its computation subgraph gouh, the SSE eu, and label
y (suppose v belongs to class k, i.e. Yo,k = 1), then training PDGNNs with e, has the following two properties:
1. It is equivalent to training PDGNNs with each node in Goub with Goub being a pseudo computation subgraph and Yo being pseudo label, where the contribution of xw (via Equation
4 in the paper) re-scaled by s(y,w:A) We term this property the pseudo-training effect neighhoring nodes.
A)
When ( 0) is linear, training PDGNNS C2 also equivalent to training (:ut(; f) on pseudo- labeled nodes (Xw, yv) for each w in G where the contribution of w in the loss is adaptively re-scaled with a weight
Energoo foet xw ( ():);;))0
Proof of Theorem I. Theorem 1 is rather intuitive and easy to understand, we still provide detailed proof for rigorousness.
Given node the prediction is:
y. = four (Cp; f)
(18)
B, = Eweyyn X (w, wi Å), where youb denotes the node set of the computation subgraph goub, and Å is the adjacency matrix of goub.
8. = fout
Σ X T(V w;; (v; A):
(19)
Vo
Given the target (ground truth label) of node as you the objective function of training the model with node v formulated as:
C, 1 Cout
Σ X T,, w. A); A):0)
(20)
WEVaub
where could be any loss function to measure the distance between the prediction and the target.
Since yaub contains both the features of node and its neighbors, Equation 20 can be further expanded to separate the contribution of node and its neighbors:
L. = 1 foue X., (
Σ Vendd (w)
X (l,, A);
(21)
information
meighhorhool information
15

---

Proof of Theorem 22 this part, we choose the loss function as cross entropy CE(-,). :). which is the common choice for classification problems. In the following, will first derive the gradient of training the PDGNNs with (e,. y.). For cross entropy, we denote the one-hu hot vector form label as y.- Given the loss of node shown in Under review as a conference paper at ICLR 2023
Given arbitrary node 9 Wer but q # E Vauh (the adjacency matrix A stays the same), similarly obtain the loss training the model with node q:
Cg
four Xy (q,
Σ
X alq w(;
(22)
information from node
we VeVVMMMM Ma}
neighhorhood information
Since y E Voub we rewrite Equation 21 as:
Lu = lout Xy ( A)
Σ
X
(23)
information from node q
We VEEEou ((a)
neighborhood information
By comparing Equation 23 and 22 we could observe the similarity in the loss of node and g, and the difference lies in the contribution (weight iT:;" A) of each node and the neighboring nodes (Vsub and Veub). To clearly explain the analysis in the paper that stronger homophily leads more benefits from pscudo training effect, we give the formal definition of the graph homophily ratio. Given graph the homophily ratio defined as the ratio of the number of edges connecting nodes with same label and the total number of edges, i.e.
(())
Σ 1(y; yk), G.R)EE
(24)
[
where is the edge set containing all edges, is the label of node j. and 1(-) is the indicator function Ma et al. (202T) For any graph, the homophily ratio is between 0 and 1. For each computation subgraph. when the homophily ratio is high, the neighboring nodes tend to share labels with the center
node, and the pseudo training would be beneficial for the performance. Many real-world graphs like the social network and citation networks tend to have high homophily ratios, and pseudo training will bring much benefit, which is shown Section 4.3 of the paper.
of which the ht element is one and other entries
16

---

Under review as a conference paper at ICLR 2023
the Equation 20 the gradient is derived as:
VoL. = VOCE
Σ
fout
Xx x (V,, w. A): A); 0):0),.r
(25)
Σ four Xws TT, wi A): 2): :)x WEVzub
Vo Yo,k log
(26)
Vo Σ Ewergus fout (Xw TVV A); 0)x²
=y,k
(27)
Eweyano fout Xw (1, wi A);
Eweyous Vofout Xw T(U,, A);
=y.k" Eweryus four Xw [(,, w; A); 0
(28)
-y,k Eweyeus Vofour : 0)): T (v, w; A)
(29)
Emeryus four Xw T(U. wE A); 0
Eegyou Yo,k Velour(xui01e fout (xwi 0)s ((U wo A) Fouc(Suil)s
(30)
Emevguh four Xw (T, wi A);
Eweyooe VoCF (Four (Xwi O), Yu.k) four (x O) T -T(V, w; A)
(31)
Emevgua faur X.i T(U, wi A):
four (x 0) T(U, W.
VOCE (Xw:
()) 8),
(32)
WENr Eweygns fout Nwm (V, wi A);
The loss of training four (Xwi 0) with pairs of feature and pscudo-label (X.. yo) of all nodes of Goub is:
Cgget
Σ
(33)
wEV
(34)
Then, the corresponding gradient of Lggue is
VoLgauh
Σ We
VoCF( (Cous (X.:; yy)
(35)
we can see that training PDGNNs with a sufficient subgraph embedding e equals to training the function (-ur(;; 0) on all nodes of the computation subgraph G with weight four (x
By comparing Equation 32 and 35
Ewerzet four Nx (p,ws))) on each node to rescale the contribution dynamically. 0
B.3 FURTHER DISCUSSION ON PSEUDO- TRAINING EFFECTS OF GENERALIZED SSE GENERATION FUNCTION
In this subsection, we give further analysis on the pseudo training effect when the SSE generation follows the following formulation:
e, = g((x
w E A).
(36)
In this scenario, the pseudo training effect will depend on the specific form of g(: Despite this, still analyze the strength of pseudo training effect with respect to the smoothness of the function and the dataset propertics. First of all, the pseudo training effect exists because the GNN models generate the prediction based local neighhorhood. Therefore, the nodes with overlapping
17

---

Under review as a conference paper at ICLR 2023
Table
The detailed statisties of datasets and task splittings
Dataset
CoraFull McCallum etal.
2000)
OGB-Arxi
Reddit (Hamilton al
2017
OGB-Productt]
nodes
19,793
169,343
232,965
2,449.029
edges
130,622
1,166,243
5,8,615,82
61,859,140
classes
47
Lasks 30/ 14/5/2
20/8
20/8/5/2
20 8/5/2
25 10/
neighborhood (similar inputs the model) share similar prediction results. If their labels are shared, then training these nodes could mutually reinforce each other. Accordingly, given an arbitrary function g(:-), .). we can gain an insight into the strength of pseudo training effect by analyzing the similarity of the inputs when generating representations of different nodes. Without loss of generality, we assume g(;;)) be continuous function (since g(.;,) does not require training, it does not have to be differentiable). Then, given two nodes e and w, denote their corresponding inputs to the model as two vectors L, and L Iy and Ly may contain different neighborhood information based on the specific form of g(. Now, it is obvious that the closer I, and I, are, the closer g(I,, A) and g A) are (due to the continuity of g). In other words, stronger homophily will lead to stronger pseudo training effect as we analyzed in Theorem in the paper. Besides, the frequency components (in terms of the spectrum of the function, e.g., with Fourier analysis) of g(:;)) also matters. g(:.) is mainly composed respect the change of the input, then the pseudo training effect is stronger because more nodes getting similar representations. But if the function g(:,)) contains strong high frequency components, i.e. -) changes significantly with the change of input, then the pseudo training effect is weaker since only very similar inputs of the nodes get similar outputs.
low frequencies, i.e., the change of -( is slow with
In experiments, also instantiated :) with the reservoir computing module (Gallicchio & Micheli 2020), which yields comparable performance with other instantiations (Section C.5)
C ADDITIONAL EXPERIMENTAL RESULTS
In this section, we provide additional information on the datasets, experimental settings, and experi- mental results.
C.I DATASET DESCRIPTIONS
The statistics of the datasets are summarized in Table Among these datasets, CoraFull and OGB- Arxiv are two citation graphs, Reddit a graph constructed from Reddit posts, and OGB-Produce is an Amazon product co-purchasing network. The usage of the datasets is granted for academic purposes, and full details on the licenses can be obtained from the official websites. The datasets contain personally identifiable information offensive content.
C.1.1 CITATION NETWORKS
CoraFull McCallum et al., 2000) a citation network labeled based on the paper topics. In total, it contains 19,793 nodes and 126,842 edges. The original dataset has 65,311 edges. We directly adopted the version in DGL with reverse edges added and duplicates removed. It contains 70 classes, and each node has 8, 8,710 dimensional feature vector.
The OGB-Arxiv dataset is collected in the Open Graph Benchmark OGB It is directed citation network between all Computer Science (CS) arXiv papers indexed by MAG (Wang et al. 2020d). Totally it contains 169,343 nodes and 1,166,243 edges. The dataset contains 40 classes.
attts: http:///ww.aanaaaaaddddd/////ede
18

---

Under review as a conference paper at ICLR 2023
Table 6: The configuration of the MLP part of PDGNNs.
No. layer
Input dimensions
Output dimensions
Activation
# data dimensions
256 classes
ReLU
2
256
SoftMax
C.1.2 SOCIAL NETWORK
Reddit Hamilton et al. (2017) is graph dataset from Reddit posts made in the month of September, 2014. The node labels are the community, or "subreddit", that the posts belong to. The authors sampled 50 large communities and built post-to-post graph, connecting posts if the same user comments on both. In total this dataset contains 232,965 nodes with an average degree of 492, 1 114,615,892 edges, and 602 dimensional feature vector for each node. We directly used the version integrated in DGL library.
C.1.3 PRODUCT CO-PURCHASING NETWORK
OGB-Products is collected in the Open Graph Benchmark F representing Amazon product purchasing network 6 It contains 2,449,029 nodes and 61,859, edges. Nodes represent products sold on Amazon, and edges indicate that the connected products are purchased together. In our experiments, we select 46 classes and omit the last class containing only example.
C.2 ADDITIONAL DETAILS ON EXPERIMENT SETUP AND MODEL EVALUATION
Continual learning setting. In this part, we give concrete examples further explain the difference between class-IL. and task-ll. scenarios. In class-IL. scenario, a model has to classify the given data by picking class from all previously learnt classes, while the task-IL IL scenario only require the model to distinguish the classes within each task. Concretely, suppose the model Iearns on a citation network with two-class task sequence {(hyysics, chemistry), (biology, math)]. J In class-IL scenario, after training, the model is required to classify given document into one of the four classes. In task-IL scenario, the model only required to classify a given document into to (physics, chemistry) or (biology, math), while cannot distinguish between physics and biology or between chemistry and math.
For each dataset, the splitting of different tasks is conducted by dividing the classes into groups in the default order. Different group sizes are shown in Table of the paper. For each task, the ratio for training. validation, and testing is 60%, 20%. 20%. The validation set only used in baseline model selection, since the hyperparameters of our method are simply set to be consistent with baselines (Section 4.2 in the paper).
Baselines and model settings. In this part, we give more details on the model configurations. The following setting applies all datasets. All the backbone GNNs of baselines configured 2-1ayer with 256 hidden dimensions, which exhibit better performance than other configurations. To ensure a fair comparison,
also set the MLP part of PDGNNs as 2-layer with 256 hidden dimensions (the SSE generation part does not contain trainable parameters) as shown in Table 6 The memory budget (number of nodes per class selected to store) is set as 400 for PDGNNS-SSESS the memory based baselines, the budget was chosen with two criteria: 1. The buffer size should be large than the size for PDGNNs-SSS SSEM ensure PDGNNs- SSEM does not succeed by storing more examples. 2. The budget should be large enough for the baseline methods to gain reasonable performance. The specific budgets on different datasets are listed in Table 7 which demonstrates that PDGNNs SEEM is actually highly efficient in using the buffered data and outperforms the memory based baselines with less memory usage. brief introduction of the baseline continual learning techniques are given below:
for all datasets. For
19

---

Under review as a conference paper at ICLR 2023
Table 7: Memory budget of different methods different datasets.
CoraFull
OGB-Arxiv
Reddit
OGB-Products
PDGNNs-SSEM
400
400
400
400
Baselines
500
500
600
700
1. Fine-tune directly trains given backbone GNN on the task sequence without any technique to avoid forgetting, therefore can be viewed as a lower bound on the continual learning performance.
2. Elastic Weight Consolidation (EWC) (Kirkpatrick et al. 2017) adds a quadratic penalty to prevent the model weights, which are important prevent model parameters related to previous tasks from shifting too much.
3. Memory Aware Synapses (MAS) (Aljundi et al., 2018 measures the importance of the parameters according to the sensitivity of the predictions the parameters and slows down the update of the important parameters.
4. Gradient Episodic Memory (GEM) (Lopez-Paz & Ranzato, 2017) data in episodic memory and adds a constraint to prevent the loss of the episodic memory from increasing and only allow it to decrease.
stores representative
5. Topology-aware Weight Preserving (TWP) (Liu et al. 2021) adds penalty the model weights to preserve the topological information of previous graphs
6. Learning without Forgetting (LwF) (Li & Hoiem 2017) uses knowledge distillation to constrain the shift of parameters for old tasks.
7. Experience Replay GNN (ER-GNN) (Zhou & Cao, 2021) integrates memory-replay to GNNs by storing experience nodes from previous tasks.
8. Joint Training does not follow the continual learning setting and trains the model on all tasks simultaneously. Therefore, Joint Training does not suffer from forgetting problems and its performance be viewed as the upper bound for continual learning.
A widely adopted performance upper bound on the continual learning models is joint training. Different from being trained sequentially on task sequence, a jointly trained model does follow the continual learning setting but is simultaneously trained on all tasks. Therefore, jointly trained models do not suffer from the forgetting problem and could be viewed as an upper bound on the continual learning performance. Note that under the class-IL setting, the average accuracy of the jointly trained model will still decrease as the number of classes increases. The reason is that the classification difficulty increases when the number of classes vary from small to large.
Class imbalance in continual graph learning. According to Equation 37 the performance on different tasks contributes equally to the average accuracy. However, unlike the traditional continual learning with balanced datasets, the class imbalance problem is usually severe in graphs, of which the effect will be entangled with the effect of forgetting. Directly balancing the data by choosing equal number of nodes from each class may not be practical. For example, in the OGB-Products dataset, the largest class has 668,950 nodes, while the smallest contains only 1 node. Therefore, sampling equal amount of nodes from each class would result in either deleting many classes without enough nodes or sampling very small number of nodes from each class so that all classes can provide the same amount of nodes. Moreover, deleting nodes in a graph would also change the original topological structures of the remaining nodes, which is undesired.
To this end, we propose to re-scale the loss of nodes in each class according to the class sizes. Denoting the set of the classes of our training data C, the number of examples of each class in C can be represented as {nc e E C}. Then, we calculate a scale for each class to balance their contribution in the loss function as Sy, E.ec mi where yo,c = 1. Finally, our balanced loss is:
C Σ ((((e;;)) 0), (.) Sy. + WEV,
Σ ESSEM
((S(ew; 0), 'yy"
(37)
Since the evaluation treats all classes equally and the loss on each class is balanced, is omitted in our implementation, it will influence the balance of each class.
20

---

Under review as a conference paper at ICLR 2023
Average accurecy/'s
80
Auerage regeentiin
Aver sge accurscy
Average forgetingg
60
-45
40
26:05
0.002
0.001
2e0g
0,0002
0,002
0.02
0000
0.0
0.001
0.01
Ratio data
Ratio of data
Ratio of data
Ratio of data
Figure 5: Average accuracy (Red circles) and average forgetting (Black crosses) changes with buffer
size on OGB-Products dataset (the left two) and Reddit dataset (the right two).
Average accuracy
Average forgentings
-10
70
50
0.001
0.01
6.8
0.011
0.01
Ratio of data
Ratio of data
Figure 6: Average accuracy (Red circles) and average forgetting (Black crosses) changes with buffer size on CoraFull dataset.
Class-incremental classifier. In standard classification tasks, the number of the output heads of a model equals the number of classes and fixed at the beginning. But class-IL. IL setting, the output heads will continually increase along with the classes. To better accommodate new classes, cosine distance adopted by several works Wu et al.) (2021); Wang et al. (2018); Gidaris & Komodakis (2018) to slightly modify the standard softmax classifier. Empirically. PDGNNs with SSEM outperform the standard softmax classifier which simply increases the output heads with the number of classes. All baselines performance over the validation set is employed for comparison. Specifically, only LwF exhibits better performance with the cosine distance based classifier.
tested with both strategies and the that achieves better
C.3 ADDITIONAL RESULTS STUDIES ON THE BUFFER SIZE
In this subsection, we show the performance of PDGNNs-SSEN with different buffer sizes on other 3 datasets in Figure and We observe similar patterns in these results, i.e., the performance (both average accuracy and average forgetting) increases when the buffer size (in terms of the ratio of data) increases. Specifically, millions of nodes, the PDGNNs-SSMM can achieve reasonably well performance with a buffer size of only 0.01 to the size of the dataset, which further demonstrates the effectiveness and efficiency of PDGNNs-SSEM.
OGB-Products dataset, which is the largest dataset with
In Table 2 of the paper, we have the following findings: (1) our coverage maximization sampling does guarantee a superior coverage ratio compared to the other sampling strategies, especially when the buffer size is relatively small; (2) the performance does exhibit strong correlation with the coverage ratio, especially when the buffer size is small. For different buffer sizes, higher coverage ratio can yield better performance. The performance gap between different sampling strategies is larger with smaller buffer sizes, which is also the situation when the coverage ratio gap is larger. In this case (buffer size smaller than I. 1.0%), the number stored SSEs is relatively small compared to the size of the dataset, therefore the effectiveness of pseudo training on more nodes is more prominent. With larger buffer sizes, all sampling strategies can cover a large ratio of nodes and the performance gaps close up. In real world upplications, smaller buffer size is typically adopted, therefore the high memory efficiency of coverage maximization sampling would be preferred. The above analysis verifies our Theorem I and indicates higher coverage ratio would be beneficial the performance.
21

---

Under review as a conference paper at ICLR 2023
1 task learned
10 task learned
20 task learned
Fine-tune
-50
-20
-0
-75
-40
-100
-100
-75
-50
-25
75
100
-40
-20
40
-40
-20
40
40
40
ER-GNNN
25-
0
-25
-50
-75
-40
-100
40
-100
-75
-30
-25
25
50
100
-40
-20
20
40
-10
-20
20
40
PDGNNs-SSEM
20-
0
-20
-0
20
400
-80
60
40
-0
80
40
-20
40
-40 -20
40
Figure 7: Visualization of node representations of different classes Reddit dataset. The node representations are taken after learning 1, 10, and 20 tasks. From the top to the bottom, we show the results of Fine-tune, ER-GNN, and PDGNNs-SSEM. Each color corresponds to class.
Average accuracy/%
100
Average accuracy/96
100
Average accuracy/%
+
ER FR-GNN
80
70
EWC
Finetune
60
60
50
40
LW/F
20
MAS
TWP
0
14
28 Classes
42
56
70
%
28
42
56
70
10
14
28
42
56
70
PD-GNNs
Classes
Classes
Joint
Figure 8: Dynamics of average accuracy CoraFull dataset with task sequence of length of 35
(left), 14 (middle), and (right) in class-IL scenario.
Average accuracy
80
Average accuracy/%
70
Average accuracy/%
100
ER-GNN
80
EWC
Finetune
GEM
30
20
TWP
0 5 15 25 Classes
100
10
20 Classes
30
40
20
40
PD-GNNs
Classes
Joint
Figure 9: Dynamics of average accuracy OGB-Arxiv dataset with task sequence of length of
(left), 4 (middle), and 2 (right) in class-IL. scenario.
22

---

Under review as a conference paper at ICLR 2023
Table Performance comparisons under class-IL L OGB-ArXi dataset with different task splittings (1 higher means better).
C.I.T.
20 tasks
8 tasks
tasks
tasks
FMM
AM/S
FM/4
1
Fine-tune
4.9::0.0
-89.740.44
10.5::0.1
-77.540..5
16.4+:0.2
-63.9:0066
26.4+0033
-47,3+:0.9
EWC
2017
8.51:10
6.0
9.4.10.1
-.3.711.11
15.710..3
62.8.0.7
24.810..3
47.5..0.6
MAS 2018
4.8:10.4
-72.2444.11
10.31:022
-77.540066
16.5400.3
64.0.0.5
26.14:0.
47.5:.0.7
GEM
4.9:00.0
-89.840.3
10.740.1
-81.540.3
18.240.2
-706:005
31.3+0.1
-58.5:0.2
TWP 2041
6.7.1.55
10.6-1
8.3.104
66.11113
14.0:10.4
17.61.
22.01044
47.6.10.5
9.9+12.1
13.6=11.9
24.2404
-31.9
19.6
1,88177
19,640,7
-51110.11
ER-GNNI022
2021
12.343.9
-79.944.11
10.9+0.2
-77.5:0.5
1988#12
1399
31,6:0.6
-34,8+1.
Joint
5684000
-8.6=0.0
55.3400.0
=0.100000
53.9:0000
-.11
51.62011
-8220.2
PDGNNs
26.841888
-61.6+200
27.91:888
-8.2422
30.91111
35.914
46,443.2
PDGNNS
53.2404
-14.740044
5164004
-1500:0.7
50.6::0.4
-12.40.55
49.740.3
-1.44005
Average accuracy/%
100
Average accuracy/%
Average accuracy/
100
-.- ER-GNN
80
EWC
70
Finetune
60
90
30
MAS
TWP
00
8
16 Classes
24
32
40
10
20 30 Classes
40
80
8
16
24 Classes
32
40
PD-GNNs
Joint
Figure 10: Dynamics of average accuracy Reddit dataset with task sequence of length of 20 (left), (middle) class-IL scenario, and Reddit dataset with task sequence of length of 20 (right) in task-IL scenario.
C.4 ADDITIONAL RESULTS OF COMPARISONS WITH THE STATE-OF-THE-ARTS
In this subsection, provide additional results to compare PDGNNs-SSEM with the baselines. In Table we provide numerical results to compare different models and complement the curves of average accuracy provided in the paper. We list both the final average accuracy and average forgetting of all models on the OGB-Arxiv dataset with different task splittings in class-IL scenario. Besides, we also show the results of PDGNNs-SSEM with an extremely small buffer size (i.e., 0.001 of the size of the dataset), which is denoted with PDGNNs 0.001 of the size of OGB-Arxiv corresponds to storing only 4 examples per class and total of 160 for 40 different classes, which is orders of magnitudes smaller than the buffer size of the memory based baselines with budgets of several hundred per class. From Table 8 we can observe that both PDGNNs and PDGNNs* significantly outperform the baselines. Even the PDGNNs can outperform basclines by large margin, which demonstrates the high efficiency of SSEM. Considering that OGB-Arxiv contains 169,343 nodes, the performance of PDGNNs* * is indeed impressive.
Since the error bars Figure in the paper are partially omitted to highlight the performance difference of different methods, we show the complete results with error bars and the results other
Average accuracy/86
100
Average accuracy/%
100
Average accuracy/%
100
90
Finetune
90
GEM
- LWF
80
MAS
70
32
80
PD-GNNs
Classes
Classes
Classes
Joint
Figure 11: Dynamics of average accuracy OGB-Arxiv dataset with task sequence of length of 20 (left) in task-IL scenario, OGB-Products dataset with task sequence of length of 23 (middle) in task-IL scenario, and FullFull dataset with task sequence of length of 35 (right).
23

---

Under review as a conference paper at ICLR 2023
Average accuracy/95
Average forgetting 1%
50
-2
-40
PDGNNs
PDGNNs
PDGNNs
PDGNNs
PDGNNs
PDGNNs
PDGNNs
-80
PDGNNs
10
0.0002
0.001
0.01
0.05
0.0002
0.001
0.01
Ratio of data
Ratio of data
Figure 12: Average accuracy (left) and average forgetting (right) vs. buffer size on OGB-Arxiv.
PDGNN' to PDGNN instantiated π [1. w; A) as the forms introduced in Section 3.4 of the paper. PDGNN4 adopts the reservoir computing module proposed in Gallicchio Micheli 2020
datasets with different task splittings (with class-IL. scenario) in Figure 8 task sequence of length is equivalent to the number of tasks to learn (as shown in Table 5 for each dataset.
9 and 10 Note that the
Besides the class-IL scenario, we also provide additional results with complete error bars for the task-IL scenario in Figure and
and 11
To show the performance difference between PDGNNS-SSEM and the baselines more concretely, we visualize the node representations of different classes with I-SNE Van der Maaten & Hinton (2008) while learning on the task sequence (with a length of 20, i.e., 20 tasks) of the Reddit dataset. In Figure besides PDGNNs-SSEM, we also show two other representative baselines including ER-GNN, specially designed for continual graph learning. and Fine-tune, without continual learning techniques. According to Figure 7 PDGNNs-SSEM can maintain the nodes from different classes be well separated while continuously learning new tasks sequentially (each color corresponds to class). In contrast, for ER-GNN and Fine-tune, the boundaries of different classes are less clear.
C.5 ADDITIONAL STUDIES ON THE BUFFER SIZE
In Figure 12 based the class-IL scenario, we study the performance of PDGNNs-SSEM the OBG-Arxiv dataset when the buffer size (i.e., the ratio of dataset) varies from 0.0002 to 0.6. Figure [2 exhibits the similar performance of different SSE generation modules. Besides, when the buffer size grows from 0.0002 to 0.01, both the average accuracy and average forgetting of PDGNNs increase. When the buffer size reaches 0.1, the performance PDGNNs comparable to the setting which stores the entire training set (when the ratio of dataset is 0.6). These results demonstrate the efficiency SSEM. Moreover, the results in Figure 12 also show that the performance difference among different SSE generation strategies is not significant,
D BROADER IMPACT
In this paper, we proposed general technique to enable GNNs which can fit into the PDGNNs framework to continually learn on expanding networks. The method can be applied to any scenario have
requiring generating node representations immediate and strong impact to address cxisting challenges for continual graph representation learning, enabling achieve state-of-the-art performance, and thus positively impacting applications on social networks, recommender systems, dynamic systems, etc.
networks. The results of this paper
Potential negative social impact may arise depending the application scenario. For example, the privacy issue should be carefully considered when dealing with data containing user information.
24


Reviews:
[{"review_id": "zQMsYa6Q8Lp", "reviewer": "Reviewer_AL85", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper presents a memory replay-based continual learning model based on simplified GNN models. When new nodes are added to the graph, the continual learning GNN keeps optimizing on both the new nodes and the old nodes in the reply buffer to avoid forgetting the historical information. The decoupling of message propagation from feature transformation enables the replay buffer to only store the target node embeddings without any neighborhood information, thus addressing the challenge of neighborhood explosion. Essentially, the proposed method is to apply decoupled GNN models to existing continual graph learning frameworks. Experiments show significant accuracy gains compared with baseline continual graph learning methods. \n", "summary_of_the_review": "Overall, although this is a well-written paper, I think it is still below the bar of acceptance due to its limited novelty and technical depth. ", "strength_and_weaknesses": "## Strengths\n\n+ The paper is clearly written and easy to read. \n+ The authors sufficiently discuss the related works in various areas, including continual learning and decoupled models. \n+ The proposed method achieves significant improvements in empirical evaluation. \n\n\n## Weaknesses\n\n- The novelty is limited. The overall idea is simple. I view it as applying decoupled GNN models to the existing continual learning pipeline. The decoupled GNNs are based on known models in the literature. \n- The theoretical results are not too significant. The usefulness of pseudo-training highly depends on the extent of homophily as well as the graph structure. If a neighbor node has a different label from the target node, then the pseudo-training effect is actually not desired. In addition, if the neighborhood of a neighbor node is different from that of a target node, then the pseudo-training will also deviate significantly from the “actual” training. \n- How do you interpret the re-scaling factor in Theorem 1. For example, why such specific form of scaling helps improve learning quality? Why it makes sense to train the \"real\" target node without re-scaling yet pseudo-train the neighbor nodes with re-scaling?\n- Although empirically working well, the proposed coverage maximization sampling is based on a straightforward heuristic.  \n- Baselines in experiments seem to be a bit out-dated. Most of them are 2017 and 2018 models. In addition, from Table 2, it seems that coverage maximization does not significantly outperform other sampling algorithms, even though the coverage ratio of other sampling algorithms is significantly lower. The leads to a question on how important is the “coverage maximization” criteria. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "sLpq_O1uECE", "reviewer": "Reviewer_zw6P", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "The paper intends to solve the memory explosion problem in the memory replay method for continual graph learning. By presenting Parameter Decoupled Graph Neural Networks (PDGNNs) with the proposed Sufficient Subgraph Embedding Memory (SSEM), the paper shows by empirical studies that the method can reduce memory space by a large margin. ", "summary_of_the_review": "The idea of compressing subgraphs into vectors is straightforward and intuitive, but the method in the paper is composed of off-the-shelf methods and lacks innovation.", "strength_and_weaknesses": "Strengths:\n1. This paper exhibits a clear logic chain to solve the memory explosion problem in the memory replay method for continual graph learning. The idea of stripping trainable parameters from the neighbor aggregation procedure is clear and effective for reducing the burden of memory replay.\n2. Exhaustive experiments are conducted to compare the proposed method with baselines. The proposed PDGNNs overwhelm other baselines across all datasets and perform close to the joint-training strategy, which is carried out as the upper bound.\n\nWeaknesses:\n1. This paper is more like to integrate various existing methods. The formulation of the PDGNN with SSEM is almost identical to that of the SGC (Simplifying Graph Convolutional Networks) method. The memory replay framework and coverage maximization sampling method almost show no differences from those of the ER-GNN paper (which is also a baseline in this paper). Consequently, this paper shows limited novelty.\n2. This paper claims that the memory replay benefits from the SSEM module by compressing information from subgraphs, which shows an advantage over the ER-GNN method. However, to the best of our knowledge, the ER-GNN method adopts the GAT network as its backbone, which also integrates information from neighbor nodes. Thus, the ER-GNN method can not be treated as a single-node buffer method. Consequently, the reason for the performance improvement over ER-GNN is not convincing and needs more explanation.\n3. Proposal of the coverage maximization sampling method is not innovative and lacks a detailed explanation in terms of two points. Firstly, the necessity of the sampling strategy requires more explanation: why not just exploit the coverage maximization method as stated in the ER-GNN paper? Moreover, the ER-GNN performs best with the influence maximization (IM) method, which is not mentioned in this paper.\n4. In terms of the proposed metrics (Average Accuracy and Average Forgetting), this paper overwhelms other baselines and almost achieves the upper bound. However, the ER-GNN paper adopts different metrics (Performance Mean and Forgeting Mean) which are not inspected in this paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EcPEWOWVhgN", "reviewer": "Reviewer_g88c", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "The paper suggests a method for buffer construction in memory replay for node classification.\nThe suggested technique reduce the space complexity of the trivial algorithm from O(nd^L) to O(n).\nThe authors also discover and define the pseudo-training effect which is unique to continual learning on non-euclidean data. Finally, the authors present a coverage maximization sampling strategy to improve their suggested continual learning technique further.", "summary_of_the_review": "From the reasons written above, I think that the novelty of the paper is relatively weak and not meets the threshold of being published in a top-tier venue.\nHence my pre-rebuttal score is (reject: 3)\n\nI expect the authors to respond to my concerns raised in the weaknesses section for my re-evaluation of this manuscript.\n ", "strength_and_weaknesses": "*Strength* \n\nThe paper aims to suggest solutions for an important real-world problem.\n\nThe suggested method outperforms previously suggested techniques for continual learning.\n\n*Weaknesses*\n\nThe contributions for the paper, as presented by the authors, are divided into three:\n\n1. PDGNNs - SSEs \n2. Pseudo-training effect discovery\n3. coverage maximization sampling strategy\n\nI will refer to each of them separately.\n\n1. The idea of decoupling the weights from the topology using two steps, in which nodes are represented as vectors, is trivial. I believe the challenge is how to encode the nodes to minimize the effect of the forgetting problem. The authors chose to encode the entire subgraph required by an MPGNN with L layers to represent the node as a vector. Their suggested technique is strongly based on previous works with minor additions. Justifications for the additions are also missing (for example, why the summation operation is being used). Moreover, different works encode subgraphs in an unsupervised manner [1,2], so a comparison is required here, in my opinion.\n\n2. The pseudo-training effect is an expected phenomenon when dealing with homophilic graphs. \nQuestion: Will the pseudo-training effect damage the performance of PDGNN - SSE on heterophilic graphs? \n\n3. The sampling method is relatively naïve, and it is not compared to any complicated sampling method presented in the literature [3,4].\nQuestion: What changes (if any) are needed to be done to fit the sampling method to heterophilic graphs?\n\n\n\nQuestion: In table 4, why PDGNNs sometimes outperform Joint?\n\n\n[1] - Sub2Vec: Feature Learning for Subgraphs, Adhikari et al.\n[2] - subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs, Narayanan et al.\n[3] - Metropolis Algorithms for Representative Subgraph Sampling, H¨ubler et al.\n[4] - Diversified Top-k Subgraph Querying in a Large Graph, Yang et al.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1Ri1kFcl44", "reviewer": "Reviewer_U4Fi", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The author propose PDGNN with SSEM for continuous graph representation learning to solve technical challenge of applying memory replay techniques to GNNs. By applying SSE, the memory space complexity was reduced, which enables PDGNN to utilize topological information sampled from previous tasks. The author also analyzed the pseudo-training effect of SSE and develop coverage-maximization sampling, which is claimed to be efficient under tight memory budgets.", "summary_of_the_review": "In conclusion, this is a good paper. I am in favor of accepting this submission.", "strength_and_weaknesses": "Strengths\nThe paper is well written.\nAs mentioned in Section 3.3, the authors noted that NL(v) typically contains O(dL) nodes, replaying n sampled nodes would require storing O(ndL) nodes, where d is the average node degree. In the Reddit dataset, which has an average degree of 492, the buffer size is easily intractable even with a small MPNN. So, directly storing computation subgraphs for memory is not feasible for GNNs. To solve this problem, the proposed method reduces the memory space by storing SSEs instead of the computation subgraphs for optimizing PDGNNs. Specifically, for a model parameterized by θ and the input Gsub v, if optimizing θ with Gsub v or ev is equivalent, then the embedding vector ev is a sufficient subgraph embedding of Gsub v. Recomputing the representation of v every time the trainable parameters are updated requires computing all nodes and edges of Gsub v. To address this issue, the authors propose the Parameter Decoupled Graph Neural Network (PDGNN) framework, which decouples trainable parameters from individual nodes/edges. Its general process is that, first, the topological information of Gsub v is encoded into the embedding vector ev through the unlearnable function ftopo( ). Next, ev is further passed into the trainable function fout(θ) to obtain the output prediction ˆyv, since the trainable parameters act on ev and not directly on any single node/edge, the model parameters θ are optimized using ev or Gsub v are equivalent. Since optimizing the SSE is equivalent to optimizing the computational subgraph of the PDGNN, the memory buffer only needs to store the SSE to reduce the space complexity from O(ndL) to O(n). This is a simple and effective method.\nIn Section 3.5, the paper mentions that SSE with larger computational graphs covering more nodes may be more efficient. The authors design a coverage-maximization sampling strategy to exploit the benefits of pseudo-training effects. The paper states that computing Rc(SSEM) for all possible SSEs in each iteration is time-consuming, especially on large graphs. Therefore, the authors propose to sample SSEs from a multinomial distribution based on the coverage of each individual SSE. Coverage-maximization sampling strategies appear to be practical.\nThe authors conducted a number of persuasive experiments. Performances under class-IL are significant.\nRelated works are properly cited.\n\nWeaknesses\nPerformance under task-IL is not good enough. It is just a little better than the previous SOTA work.\nYou'd better write the contribution of the paper in the form of bullet points, the writing style of the last paragraph in the first section is not easy to read.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject