# Towards Robust Inductive Graph Incremental Learning via Experience Replay

Junwei Su
Department of Computer Science
The University of Hong Kong
<EMAIL_ADDRESS>
&Chuan Wu
Department of Computer Science
The University of Hong Kong
<EMAIL_ADDRESS>

###### Abstract

Inductive node-wise graph incremental learning is a challenging task due to
the dynamic nature of evolving graphs and the dependencies between nodes. In
this paper, we propose a novel experience replay framework, called Structure-
Evolution-Aware Experience Replay (SEA-ER), that addresses these challenges by
leveraging the topological awareness of GNNs and importance reweighting
technique. Our framework effectively addresses the data dependency of node
prediction problems in evolving graphs, with a theoretical guarantee that
supports its effectiveness. Through empirical evaluation, we demonstrate that
our proposed framework outperforms the current state-of-the-art GNN experience
replay methods on several benchmark datasets, as measured by metrics such as
accuracy and forgetting.

##  1 Introduction

Humans possess the ability to continuously acquire new knowledge while
retaining previously obtained information. This seemingly effortless
capability, however, is challenging but crucial for deep neural networks
(DNNs) to achieve. Incremental learning, also known as continual learning or
lifelong learning, are machine learning approaches that enable a model to
continuously acquire new knowledge while retaining previously obtained
knowledge. This is important as it allows the model to adapt to new
information without forgetting past knowledge. In the general formulation of
incremental learning, a stream of tasks arrive sequentially, and the model
goes through rounds of training sessions to accumulate knowledge for a
particular objective, such as classification. The goal is to find a learning
algorithm that can incrementally update the model’s parameters based on the
new task without suffering from “catastrophic forgetting” McCloskey and Cohen
(1989), which refers to the inability to retain previously learned information
when learning new tasks. Incremental learning is crucial for the practicality
of machine learning systems because it allows the model to adapt to new
information without the need for frequent retraining, which can be costly.

While incremental learning has been extensively studied on Euclidean data
(e.g., images), there has been relatively little research on incremental
learning on graph-structured data. Graphs are often generated/updated
continuously in real-life scenarios, such as online social networks, traffic
networks and financial networks, making them an ideal application for
incremental learning. For example, in a citation network, new papers and their
associated citations may emerge, and a document classifier needs to
continuously adapt its parameters to distinguish the documents of newly
emerged research fields. Similarly, in social networks, the dynamics of users’
friendships and activities change over time. In financial networks, the
payment flows between transactions and the appearance of illicit transactions
have strong correlations with external contextual factors like the time and
the market. Therefore, it is important to develop Graph Incremental Learning
(GIL) methods that can handle new tasks over newly emerged graph data while
maintaining model performance, especially for Graph Neural Networks (GNNs),
which have become the “de-facto” neural model for graph data.

However, applying incremental learning to graph data is challenging,
particularly for problems that involve prediction tasks for each individual
node, which introduces non-independent and non-identically distributed
characteristics in the data generation process. In addition to node features,
the structural information of the graph is part of the input to GNNs and can
affect the model’s generalization ability. This presents unique technical
challenges for the node prediction problem in GIL, particularly when the
underlying graph structure is evolving. Under an evolving graph, new vertices
and edges are constantly added, altering the connectivity of existing vertices
from one learning task to the next. We refer to this setting as the inductive
NGIL (Node-wise GIL) problem, which poses unique challenges in terms of
adapting previously learned information to new structural information in an
evolving graph.

An effective framework for addressing catastrophic forgetting of incremental
learning on Euclidean data is “experience replay” Rolnick et al. (2018), which
stores a set of nodes as experiences in a buffer and replays them in
subsequent learning tasks. This allows the system to consolidate past
knowledge, providing the capability of alleviating catastrophic forgetting.
However, the reliance of GNNs on graph structure and the challenges of
evolving graph structures render the existing experience replay framework
ineffective. In this paper, we propose a novel experience replay framework for
inductive NGIL with GNNs, which addresses these challenges and provides a
theoretical guarantee for addressing the data dependency of node prediction
problems in evolving graphs. Our experimental studies show that our proposed
framework outperforms current state-of-the-art GNN experience replay
frameworks in the inductive NGIL problem. The main contributions of this paper
are summarized as follows.

  1. 1.

We present the inductive NGIL paradigm and formulate an incremental learning
problem for node classification with a continually evolving graph. The main
difference is that previous graph incremental learning works focus on a
transductive setting where graph structures between tasks are assumed to be
independent.

  2. 2.

We develop a novel experience replay framework, called Structure-Evolution-
Aware Experience Replay (SEA-ER), that addresses the issues of catastrophic
forgetting and the unique challenges (introduced in Sec. 3.3) posed by
inductive NGIL. Our framework is based on the topology awareness of GNNs,
which allows the model to take into account the structural information of the
graph, and provides a theoretical guarantee for addressing the catastrophic
forgetting problem in NGIL.

  3. 3.

We conduct an empirical study to demonstrate the effectiveness of our proposed
approach. The results of the study show that our proposed experience replay
framework effectively addresses the problem of changing structure and
catastrophic forgetting, and outperforms existing state-of-the-art experience
replay framework for GNNs Zhou and Cao (2021a); Ahrabian et al. (2021) in
inductive NGIL.

##  2 Related Work

###  2.1 Incremental Learning

Incremental learning, also known as continual or lifelong learning, has gained
increasing attention in recent years and has been extensively explored in
Euclidean data. We refer readers to the surveys Delange et al. (2021); Parisi
et al. (2019); Biesialska et al. (2020) for a more comprehensive review of
these works. The primary challenge of incremental learning is to address the
catastrophic forgetting problem, which refers to the drastic degradation in a
model’s performance on previous tasks after being trained on new tasks.

Existing approaches for addressing this problem can be broadly categorized
into three types: regularization-based methods, experience-replay based
methods, and parameter-isolation-based methods. Regularization-based methods
aim to maintain the model’s performance on previous tasks by penalizing
changes in the model parameters through regularization terms Jung et al.
(2016); Li and Hoiem (2017); Kirkpatrick et al. (2017); Farajtabar et al.
(2020); Saha et al. (2021). Parameter-isolation-based methods prevent drastic
changes to the parameters that are important for previous tasks by continually
introducing new parameters for new tasks Rusu et al. (2016); Yoon et al.
(2017, 2019); Wortsman et al. (2020); Wu et al. (2019). Experience-replay
based methods select a set of representative data from previous tasks, which
are used to retrain the model with the new task data to prevent forgetting
Lopez-Paz and Ranzato (2017); Shin et al. (2017); Aljundi et al. (2019);
Caccia et al. (2020); Chrysakis and Moens (2020); Knoblauch et al. (2020).

In this paper, we focus on the usage of experience replay for its simplicity
and effectiveness. As we discuss in Sec. 3.3, there are unique challenges,
namely structural bias and structural dependency, posed by inductive NGIL,
rendering the existing experience replay framework unsuitable in this case.
Therefore, in this paper, we propose a tailored design of experience replay
for inductive NGIL.

###  2.2 Incremental Learning with Graph Neural Network

Recent advancements in GNNs have led to a surge of interest in GIL due to its
practical significance Wang et al. (2022); Xu et al. (2020); Daruna et al.
(2021); Kou et al. (2020); Ahrabian et al. (2021); Cai et al. (2022); Wang et
al. (2020); Liu et al. (2021); Zhang et al. (2021); Zhou and Cao (2021b);
Carta et al. (2021). For a comprehensive overview of existing GIL methods and
their effectiveness, we refer readers to a recent benchmark paper Zhang et al.
(2022). Studies that are closely related to this work include Ahrabian et al.
(2021); Zhou and Cao (2021b). Zhou and Cao (2021b) has shown the feasibility
and effectiveness of the experience replay framework in addressing the
catastrophic forgetting problem in NGIL. However, their experience buffer
selection is mostly based on node features or representation, and neglects the
graph structure. On the other hand, Ahrabian et al. (2021) takes into account
the topological awareness of GNNs and proposes an experience buffer selection
based on the node degree.

There are three key distinctions between our work and these two studies.
First, as discussed in Zhang et al. (2022), these two studies are restricted
to a transductive setting, where the underlying graph structure is assumed to
be independent throughout the learning process. This assumption neglects the
structural dependency issue (introduced in Sec. 3.3) of graph structure when
transitioning to a new task, which requires specific treatment. Second, our
proposed experience buffer selection relies on a more sophisticated graph
structure and offers a theoretical guarantee that ensures consistent long-term
performance. Lastly, instead of simply blending the experience buffer with the
training set, we propose a novel replay method with importance reweighting for
addressing the structural dependency problem.

Finally, it is important to note that there is another area of research known
as dynamic graph learning, which focuses on GNNs that can capture the changing
graph structures. We refer the reader to Kazemi et al. (2020) for a more
comprehensive survey. The goal of dynamic graph learning is to capture the
temporal dynamics of the graph and continuously update the graph
representations, while having access to all previous information. In contrast,
GIL addresses the problem of catastrophic forgetting, in which the model’s
performance on previous tasks degrades after learning new tasks and the data
from previous tasks is inaccessible or has limited access. As a result, during
evaluation, a dynamic graph learning algorithm is only tested on the latest
data, while GIL models are also evaluated on past data.

##  3 Preliminaries, Problem Formulation and Challenges

In this section, we introduce the formulation of the inductive NGIL problem,
GNNs, and experience replay framework.

The inductive NGIL problem involves a collection of $m$ tasks
$\mathcal{T}=\\{\mathcal{T}_{1},\mathcal{T}_{2},...,\mathcal{T}_{m}\\}$ that
are encountered sequentially, where each $\mathcal{T}_{i}\in\mathcal{T}$ is a
node classification task. Formally, a node classification task is defined as:

######  Definition 1.

For each node classification task $\mathcal{T}_{i}$, there is a training node
set $\mathcal{V}^{train}_{i}$ and a testing node set $\mathcal{V}^{test}_{i}$.
The goal of the learning task is to learn a task-specific classifier
$f_{\mathcal{T}_{i}}$ from $\mathcal{V}^{train}_{i}$ that correctly classifies
each vertex $v\in\mathcal{V}^{test}_{i}$ into its correct label
$y_{v}\in\mathcal{Y}_{i}$, where
$\mathcal{Y}_{i}=\\{y_{1}^{i},y_{2}^{i},...,y_{k}^{i}\\}$ is the label set and
$k$ is the number of classes in $\mathcal{T}_{i}$.

We consider an inductive setting where the task collection $\mathcal{T}$ is
drawn from an unknown undirected graph $\mathcal{G}$. Let $\mathcal{V}_{i}$
denote the set of vertices associated with $\mathcal{T}_{i}$. Then the
observed graph structure at task $\mathcal{T}_{i}$ is induced by the
cumulative vertices from all encountered tasks before, and is given by:
$\mathcal{G}_{\mathcal{T}_{i}}=\mathcal{G}[\bigcup_{j=1}^{i}\mathcal{V}_{j}].$
In this setting, the graph structure evolves as the learning progresses
through different training tasks. We have:
$\mathcal{G}_{\mathcal{T}_{i}}\subset\mathcal{G}_{\mathcal{T}_{i+1}},\forall
i\in 1,...,m-1.$

Fig. 1 provides a graphical illustration. This setting is significantly
different from the transductive setting which assumes the complete graph
structure is known throughout each task. We further discuss how the indutive
setting is different in the next section.

Figure 1: An Illustration of inductive NGIL. For each new task, the graph
structure evolves and expands. The different coloured vertexes within each
task represent the different classes/labels within the classification task.
The vertexes highlighted in red are the vertexes whose neighbourhoods are
altered by the expansion process. The overlapped region indicates that a
vertex can belong to more than one task.

###  3.1 Graph Neural Network

GNNs are a class of neural networks that operate on graph-structured data.
They adopt a neighbourhood aggregation scheme, where the representation of a
node is updated iteratively by aggregating representations of its neighbours.
After $k$ iterations of aggregation, a node’s representation captures the
structural information within its k-hop neighborhood in the graph. Formally,
the k-th layer of a GNN can be written as follows:

$h_{u}^{(k)}=\text{Update}^{(k)}(\text{Aggregate}^{(k)}({h_{v}^{(k-1)},\forall
v\in\mathcal{N}(u)\cup{u}})),$ (1)

where $h_{u}^{(k)}$ is the representation vector of node $u$ at the k-th
layer, $h_{u}^{(0)}$ is initialized to be the node feature of vertex $x_{u}$,
and $\mathcal{N}(u)$ is the set of nodes adjacent to $u$. Different GNNs are
compositions of these aggregation and update layers with different designs.
Such a neighborhood scheme allows GNNs to capture structural information of a
given vertex. In node classification tasks, GNNs are used as an embedding
function (to capture topology information) along with some task-specific
prediction functions to form the task-specific classifier. More formally, we
refer to $\mathcal{M}$ as a given GNN model and $f_{\mathcal{T}_{i}}$ as the
task-specific classifier for task $\mathcal{T}_{i}$. Then the predicted
classification of vertex $v$ from task $\mathcal{T}_{i}$ is given by
$\hat{y_{v}}=f_{\mathcal{T}_{i}}(\mathcal{M}(v))$.

###  3.2 Experience Replay Framework

Experience replay is a method inspired by the Complementary Learning Systems
(CLS) theory, which suggests that human learning involves a virtual experience
system that replays stored memory to continually reinforce tasks that have
been recently performed McClelland et al. (1995); Kumaran et al. (2016). The
idea of experience replay is to select a small subset of representative data
samples from the past and to replay them in each new learning task to
consolidate past knowledge. Experience replay methods involve two main
components: 1) selecting an experience buffer that stores important samples
from the past and 2) deciding how the experience buffer is replayed (trained)
with the new task.

Given a loss function $\mathcal{L}$, let $\mathcal{L}(v)$ denote the loss for
vertex $v$. $\mathcal{P}_{i}=\\{P_{1},...,P_{i-1}\\}$ denotes the experience
buffer accumulated before task $\mathcal{T}_{i}$ and $P_{j}\in\mathcal{P}_{i}$
is the replay samples selected from task $\mathcal{T}_{j}$ based on certain
strategy. Then, a standard experience replay framework amounts to the
following learning objective:

$\mathcal{L}=\frac{1}{|\mathcal{V}^{\text{train}}_{i}|}\sum_{v\in\mathcal{V}^{\text{train}}_{i}}\mathcal{L}(v)+\sum_{P_{j}\in\mathcal{P}_{i}}\frac{1}{|P_{j}|}\sum_{v\in
P_{j}}\mathcal{L}(v),$ (2)

where $\mathcal{V}^{\text{train}}_{i}$ is the training set for task
$\mathcal{T}_{i}$.

###  3.3 Unique Challenges in NGIL

Structural Dependency. The structural dependency of the graph structure among
different tasks poses a significant challenge in the inductive NGIL setting.
As the system is tasked with learning from a set of node classification tasks
that arrive sequentially, it must continuously acquire new knowledge while
retaining previously obtained knowledge. However, the appearance of new
vertices from new tasks can expand the previous graph structure and alter the
dependencies among vertices in previous tasks. This can lead to a fundamental
change in the information learned by GNNs, as they rely on neighborhood
aggregation to learn representations for each vertex. This is further
illustrated in Fig. 2, where the 2-hop ego graph of a red vertex $v$ has
changed significantly with the addition of new vertices from a new task. On
the other hand, in a transductive setting, the ego graph of vertices stays the
same. In other words, structural dependency can induce a distributional shift
in the information learned from previous tasks in the inductive setting and
needs to be addressed in the experience replay method.

Structural Bias. In addition to considering the structural dependency of the
graph, it is also important to address the issue of structural bias of GNNs in
NGIL, particularly, for selecting the experience buffer. Structural bias
refers to the tendency of GNNs to exhibit unfair behaviour towards different
structural subgroups (subgroups defined by a graph structure such as distance)
within the data Ma et al. (2021); Zhu et al. (2021). This can result in a
large variance in the performance of GNNs when trained on different subsets of
vertices, particularly when the number of samples is small, as is the case
with experience replay. To avoid this, it is important to carefully select a
representative sample from the past for experience replay, taking into account
the structural properties of the data and the predictive power of GNNs.

Figure 2: An Illustration of Structural Dependency Issue in the Inductive NIGL
and the Difference from the Transductive Setting.

##  4 Structure-Evolution-Aware Experience Replay

In this section, we present Structure-Evolution-Aware Experience Replay
Framework (SEA-ER) which combines the topology awareness of GNNs and the
importance reweighting for addressing the challenges in the NGIL problem.

###  4.1 Experience Buffer Selection

Recall that $\mathcal{P}_{i}=\\{P_{1},...,P_{i-1}\\}$ is the experience buffer
for $\mathcal{T}_{i}$ and $P_{j}\in\mathcal{P}_{i}$ is the replay samples
selected from task $\mathcal{T}_{j}$. According to the structural bias
discussed in Sec. 3.3, the structural position of the replay set in the graph
is important for selecting a (representative) replay set that can generalize
well to the rest of the vertexes for the task. To address this issue, we
propose a replay set selection strategy based on the idea of selecting replay
samples that have the closest structural similarity to the rest of the
vertices, and it is given as follows.

$\begin{split}\min_{P_{j}\subset\mathcal{V}_{j}}\max_{u\in\mathcal{V}_{j}\backslash
P_{j}}\min_{v\in P_{j}}d_{\text{spd}}(u,v)\quad s.t.|P_{j}|=b.\end{split}$ (3)

$d_{\text{spd}}(.)$ is the shortest path distance and $b$ is the number of
samples (experience) to select from each task. Intuitively, the larger the $b$
is, the better the performance of the experience replay method as it can be
benefited from seeing more samples from the past. The size of $b$ is a system
constraint dependent on the size of storage that the system has prepared for
storing the past experience. However, as illustrated in our empirical study as
well as others Zhang et al. (2022), experience replay method is generally
effective even with a small $b$. Eq. 15 amounts to the k-center problem in
network and is NP-hard. However, there exists a wide branch of heuristic
methods. We defer the heuristic procedure we used for solving Eq. 15 to the
appendix.

###  4.2 Replay with Importance Reweighting

As we discuss in Sec. 3.3, the structural dependency issue could alter the
distribution from the previous task. To address the issue, we propose a novel
replay method with importance reweighting. It reduces the distributional shift
by adjusting the importance of individual examples in the training. Here, we
use importance reweighting when replaying the experience buffer to address the
distribution shift induced by the structural dependency issue. Formally, let
$\mathbf{H}\subset\mathds{R}^{n}$ be the embedding space for the learned
representation of vertices. Let $\mathcal{M}:v\mapsto\mathbf{H}$ be a specific
instance of a GNN model that maps a vertex $v$ to a representation vector
$h_{v}$ in the embedding space $\mathbf{H}$. Replay with reweighting amounts
to the following learning objective,

$\mathcal{L}=\frac{1}{|\mathcal{V}^{\text{train}}_{i}|}\sum_{v\in\mathcal{V}^{\text{train}}_{i}}\mathcal{L}(v)+\sum_{P_{j}\in\mathcal{P}_{i}}\frac{1}{|P_{j}|}\sum_{v\in
P_{j}}\beta_{v}\mathcal{L}(v),$ (4)

where $\beta_{v}$ is the weight for vertex $v$ in the experience buffer. Then
the optimal $\beta$ (collection of $\beta_{v}$) can be computed through kernel
mean matching (KMM) Gretton et al. (2009) by solving the following quadratic
problem,

$\begin{split}\min_{\beta}||\sum_{P_{j}\in\mathcal{P}_{i}}\sum_{v\in
P_{j}}\beta_{v}\phi(h_{v})-\phi(h_{v})^{\prime}||^{2},s.t.B_{l}\leq\beta_{v}<B_{u},\end{split}$
(5)

where $h_{v}$ is the node embedding (output of the GNN) with respect to
$\mathcal{G}_{\mathcal{T}_{i}}$ and $h_{v}^{\prime}$ is the node embedding
with respect to $\mathcal{G}_{\mathcal{T}_{i-1}}$. Importance reweighting
tries to match the mean elements in a kernel space $\mathcal{K}(.,.)$ on the
domain $\mathbf{H}\times\mathbf{H}$. $\phi$ is the feature map to the
reproducing kernel Hilbert space(RKHS) introduced by kernel $k$. A common
choice for the kernel $\mathcal{K}$ is a mixture of gaussian kernel
$\mathcal{K}(x,y)=\sum_{\alpha_{i}}e^{-\alpha_{i}||x-y||_{2}}$ and we use
$\alpha_{i}=1,0.1,0.01$ in our experiment. The lower bound $B_{l}$ and upper
bound $B_{u}$ constraints are to ensure reasonable weight for most of the
instances. The overall learning procedure of our framework is given in
Algorithm 1.

Algorithm 1 Learning Procedure for $\mathcal{T}_{i}$

0: $\mathcal{V}^{\text{train}}_{i}$ //training set for $\mathcal{T}_{i}$

0: $\mathcal{P}_{i}=\\{P_{1},...,P_{i-1}\\}$ //replay buffer for tasks
$\mathcal{T}_{i}$

0: $\mathcal{M}$ //GNN model and prediction head for each task//compute the
representation for vertice in the experience buffer before and update updating
the graph
$h_{\mathcal{P}_{i}}=\mathcal{M}(\mathcal{P}_{i}|\mathcal{G}_{\mathcal{T}_{i-1}}),h_{\mathcal{P}_{i}}^{\prime}=\mathcal{M}(\mathcal{P}_{i}|\mathcal{G}_{\mathcal{T}_{i}})$
//compute weight $\beta$ of each vertex in the experience buffer through Eq.
5// Run training procedure (e.g. BackProp) with loss function:
$\mathcal{L}=\frac{1}{|\mathcal{V}^{\text{train}}_{i}|}\sum_{v\in\mathcal{V}^{\text{train}}_{i}}\mathcal{L}(v)+\sum_{P_{j}\in\mathcal{P}_{i}}\frac{1}{|P_{j}|}\sum_{v\in
P_{j}}\beta_{v}\mathcal{L}(v).$

##  5 Theoretical Analysis

In this section, we present a theoretical analysis of our proposed method by
using the distortion rate between the graph domain and the embedding domain to
provide a theoretical guarantee. We begin by introducing the definitions and
assumptions used in our analysis.

We make the following assumptions for our analysis:

  * •

A1: the loss function $\mathcal{L}$ is bounded, continuous and smooth

  * •

A2: the learning tasks are generated from a smooth distribution

These two are common assumptions used in generalization analysis to make the
analysis feasible. We use the notion of distortion rate to characterize the
topology awareness of GNNs. It is mathematically defined as follows:

######  Definition 2 (distortion rate).

Given two metric spaces $(\mathcal{Q},d)$ and
$(\mathcal{Q^{\prime}},d^{\prime})$ and a mapping
$\gamma:\mathcal{Q}\mapsto\mathcal{Q^{\prime}}$, $\gamma$ is said to have a
distortion $\alpha\geq 1$, if there exists a constant $r>0$ such that $\forall
u,v\in\mathcal{E}$, $rd(u,v)\leq d^{\prime}(\gamma(u),\gamma(v))\leq\alpha
rd(u,v)$.

Distortion rate is the ratio of the distance in the embedding space to that in
the original space. A low distortion rate (close to 1) indicates that the
embedding preserves the corresponding structural information from the original
space. This allows us to theoretically analyze our experience selection
strategy with respect to the topology awareness (structural bias) of GNNs. The
aggregation designs of modern GNNs exploit homophily Zhu et al. (2020) and
feature smoothing Li et al. (2018). As a result, the distortion rate $\alpha$
with respect to graph distance is expected to be small, at least within the
localized neighborhood. We further validate this empirically in the next
section.

We then present the main theoretical result of this paper, which provides a
long-term performance guarantee for our proposed experience selection
strategy. Let
$R^{\mathcal{L}}(\mathcal{V})=\mathds{E}_{v\sim\mathcal{V}}\mathcal{L}(v)$
denote the expected loss on a given vertex set $\mathcal{V}$.

######  Theorem 1.

Given a collection task $\mathcal{T}_{1},...,\mathcal{T}_{m}$ and their
associated vertex set $\mathcal{V}_{1},...,\mathcal{V}_{m}$. Let
$\mathcal{P}_{m}=\\{P_{1},...,P_{m-1}\\}$ be the experience buffer selected by
solving Eq. 15 where each $P_{i}\in\mathcal{P}_{m}$ has the same cardinality
and cover all classes in $\mathcal{T}_{i}$. Let $\mathcal{M}$ be the GNN model
with distortion rate $\alpha$. For all task $\mathcal{T}_{i}$ with a smooth
task classifier $f_{\mathcal{T}_{i}}$, we have that

$R^{\mathcal{L}}(\mathcal{V}_{i}\backslash P_{i})\leq
R^{\mathcal{L}}(P_{i})+\mathcal{O}(\alpha D_{s}(\mathcal{V}_{i}\backslash
P_{i},P_{i})),$

where

$D_{s}(\mathcal{V}_{i}\backslash
P_{i},P_{i})=\max_{u\in\mathcal{V}_{i}\backslash P_{i}}\min_{v\in
P_{i}}d_{\text{spd}}(v,u),$

We provide a proof for Theorem 1 in the appendix. Theorem 1 states that given
an experience buffer selected by solving Eq. 15, the generalization risk of
the model in the past data (catastrophic forgetting) is bounded by the
training loss (on the experience buffer) and a product factors from the
distortion of the model and the structural distance of experience buffer. The
theorem provides a performance guarantee for our proposed experience selection
strategy, with the structural distance being a key influencing factor in the
performance bound. Additionally, the theorem highlights the importance of
considering the graph structure when selecting the proper replay sets.

Table 1: Dataset settings.  Datasets | Cora | CoauthorCS | Reddit
---|---|---|---
$\\#$ Vertexes | 2,708 | 18,333 | 232,965
$\\#$ Edges | 10,556 | 327,576 | 114,615,892
$\\#$ Node Feature | 1,433 | 6,805 | 602
$\\#$ Class | 7 | 15 | 41
$\\#$ Tasks | 3 | 5 | 8
$\\#$ Class per Task | 2/3 | 3 | 5/6

(a) GraphSAGE, Cora

(b) GraphSAGE, CoauthorCS

(c) GraphSAGE, Reddit

Figure 3: Graph distance vs. embedding distance.

(a) Cora

(b) CoauthorCS

(c) Reddit

Figure 4: Task 1’s performance in evolving and constant graphs. Table 2: Performance comparisons under inductive NGIL on different datasets($\uparrow$ higher means better). Results from three trials.  Dataset | Cora | Coauthor CS | Reddit
---|---|---|---
Performance Metric |  ATP (%) $\uparrow$ |  ATF (%) $\uparrow$ |  ATP (%) $\uparrow$ |  ATF (%) $\uparrow$ |  ATP(%) $\uparrow$ |  ATF (%) $\uparrow$
Bare model |  61.41 $\pm$ 1.2 |  -30.36 $\pm$ 1.3 |  59.24 $\pm$ 3.6 |  -33.72 $\pm$ 3.3 |  68.60 $\pm$ 1.8 |  -23.87 $\pm$ 1.7
Joint Training |  92.34 $\pm$ 0.6 | N.A. |  94.36 $\pm$ 0.4 | N.A. |  85.27 $\pm$ 1.2 | N.A.
ER:IID-Random |  77.24 $\pm$ 5.8 |  16.73 $\pm$ 5.6 |  79.72 $\pm$ 4.6 |  14.89 $\pm$ 4.5 |  73.08 $\pm$ 3.3 |  21.89 $\pm$ 2.5
ER-deg Ahrabian et al. (2021) |  86.24 $\pm$ 0.7 |  -8.73 $\pm$ 0.7 |  85.3 $\pm$ 0.8 |  -10.89 $\pm$ 1.9 |  75.08 $\pm$ 0.9 |  -19.89 $\pm$ 0.9
ER-rep Zhou and Cao (2021a) |  88.95 $\pm$ 0.9 |  -7.55 $\pm$ 0.8 |  88.12 $\pm$ 0.9 |  -8.23 $\pm$ 0.9 |  78.29 $\pm$ 1.2 |  -15.21 $\pm$ 1.3
SEA-ER (ours) |  89.13 $\pm$ 0.8 |  -7.21 $\pm$0.9 |  89.19 $\pm$ 0.7 |  -7.13 $\pm$ 0.5 |  79.48 $\pm$ 1.7 |  -14.10 $\pm$ 1.6
SEA-ER-re (ours) |  91.67 $\pm$ 1.3 |  -4.01 $\pm$ 1.4 |  92.88 $\pm$ 1.1 |  -3.08 $\pm$ 0.7 |  81.89 $\pm$ 1.5 |  -9.72 $\pm$ 1.4

##  6 Evaluation

In this section, we present an empirical evaluation of our proposed experience
replay framework for GNNs. Through a series of experiments, we aim to answer
the following questions: (1) Does the distortion rate of GNNs, as discussed in
Theorem 1, hold true in practice? (2) Does the structural dependency issue, as
discussed in Sec. 3.3, have a significant impact on the generalization
performance of GNNs in the inductive NGIL setting? (3) How does our proposed
experience replay framework compare to existing experience replay methods for
GNNs Zhou and Cao (2021a); Ahrabian et al. (2021)?

General setup. We implement our experiments using the Deep Graph Library (DGL)
Wang et al. (2019) and use three representative GNNs: GCN Kipf and Welling
(2017), GraphSAGE Hamilton et al. (2018), and GAT Veličković et al. (2017). We
also adopt part of the experiments from a recent GIL benchmark paper Zhang et
al. (2022). We use three popular and publicly available graph benchmarking
datasets: Cora, CoauthorCS, and Reddit. Due to space limitations, we defer a
more detailed description of the experiment setup, dataset and GNN models to
the supplementary material.

Distortion Rate. We first validate that the distortion rate of GNNs is small.
We train a vanilla GraphSAGE model using the default setting of each dataset
provided in DGL. We extract the vertices from the local neighbourhood around
each training vertex and group them by hop distance, and show the average
Euclidean distance between the embeddings of the vertices in each group and
their closest embeddings of training vertexes in Fig. 3. In the figure, the
distortion rate and scaling factor of the GNN are reflected by the slope of
the near-linear relation between the embedding distance and the graph
distance. We can see that the distortion factors in the performance bound in
Theorem 1 are indeed small.

Incremental Learning Setting. In this paper, we consider an inductive NGIL
setting. We follow closely the setting used in Zhou and Cao (2021a); Zhang et
al. (2022), except that we gradually grow the graph with data from each task
(inductive) while they assume a constant graph structure (transductive). We
evenly divide the classes in each dataset to form each w-class classification
task. For example, there are 7 classes in Cora and we divide them into three
tasks: Task 1 is a 2-class classification task between classes 0 and 1, task 2
between classes 2 and 3, and task 3 between classes 4,5 and 6. At each
learning stage (task), the system only has access to the graph induced by the
vertices at the current and earlier learning stages, following the formulation
in Sec. 3. A brief description of the datasets, and how they are divided into
different node classification tasks is given in Table 1.

Evaluation Metrics. We use two common metrics, the average task performance
(ATP) and average task forgetting (ATF) Zhang et al. (2022), to evaluate and
compare the effectiveness of our proposed methods. Let $R_{i}^{j}$ denote the
classification accuracy of task $\mathcal{T}_{i}$ at task $\mathcal{T}_{j}$
($j\geq i$) and $m$ denote the total number of tasks. Then ATP, the average
classification accuracy of all the tasks, is computed as follows:
$\text{ATP}=\frac{\sum_{i\in 1,...,m}R_{i}^{m}}{m}.$ ATF, the average
forgetting performance, is computed as $\text{ATF}=\frac{\sum_{i\in
1,...,m-1}R_{i}^{i}-R_{i}^{m}}{m-1}.$

Comparison with Baselines. In this experiment, we adopt the standard multi-
head architecture (as illustrated in Fig. 5 used in increment learning. We use
a vanilla GraphSage as the based module for multi-head architecture. We
compare the performance of SEA-ER with various baselines. Bare model denotes
the backbone GNN without incremental learning technique. Therefore, this can
be viewed as the lower bound for incremental learning performance. Joint
Training does not follow the incremental learning setting and trains the
backbone GNN on all tasks simultaneously. Therefore, Joint Training has no
forgetting problems and its performance can be viewed as the upper bound for
continual learning. ER-IID-Random Zhou and Cao (2021a) updates each task with
learning objective Eq. 2 and experience buffer is randomly selected from each
task. This serves as a baseline for showing the effectiveness of different
experience buffer selection strategies. We also adopt the state-of-the-art
experience replay framework for GNNs for comparison. ER-rep Zhou and Cao
(2021a) updates each task with learning objective Eq. 2 and experience buffer
is selected based on the representations of the vertex. ER-deg Zhou and Cao
(2021a) update each task with learning objective Eq. 2 and an experience
buffer selected based on the degree of vertices. We adopt the implementation
of these two baselines form the benchmark paper Zhang et al. (2022). SEA-ER is
our proposed experience replay selection strategy with the same learning
objective Eq. 2 and SEA-ER-re is our proposed experience replay selection
strategy with learning objective Eq. 4. As shown in Table 2, our experience
buffer selection strategy, SEA-ER, outperforms ER-rep and ER-deg in the
inductive setting. In addition, the modified learning objective Eq. 4 further
boosts the performance by adjusting the distribution difference.

Figure 5: Multi-head GNN Architecture. Graph data are fed into the GNN module;
generated node representations are passed to the corresponding prediction
head(s) based on its associated task index(es).

Structural Dependency. To further illustrate the structural dependency of
inductive NGIL and its difference with the transductive setting, we plot the
learning dynamics of the first two tasks from the Bare model above. In Fig. 4,
$T_{1}$ and $T_{2}$ on the x-axis denote the first and the second learning
stages, respectively, and $T_{2}-$ represents the state when Task 2 has
arrived but the model has not been trained on Task 2 data yet. As shown in the
figure, in the case of an evolving graph (inductive), the model performance on
Task 1 experiences two drops when entering stage 2: when vertices of Task 2
are added to the graph (structural dependency) and when the model is trained
on Task 2’s data. Because of the structural dependency, the performance of
task-incremental learning on an evolving graph is different from that on a
constant graph where the complete graph (from the entire dataset) is available
from the beginning. This differentiates inductive NGIL from other incremental
learning problems, including NGIL on constant graphs.

##  7 Conclusion and Discussion

In this paper, we present a comprehensive study on node-wide graph incremental
learning on evolving graphs (inductive NGIL). We propose an experience replay
framework (SEA-ER) that effectively addresses the issues of structural bias
and structural dependency that arise in this problem. Theoretical analysis and
empirical results validate the effectiveness of our proposed approach and
provide a foundation for further research in this area.

One limitation of this work is that we only consider the evolving graph for
our inductive setting. Analyzing and developing frameworks for inductive GIL
with a larger range of dynamic processes renders a challenging and interesting
research direction.

## References

  * Ahrabian et al. [2021] K. Ahrabian, Y. Xu, Y. Zhang, J. Wu, Y. Wang, and M. Coates.  Structure aware experience replay for incremental learning in graph-based recommender systems.  In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_, pages 2832–2836, 2021.
  * Aljundi et al. [2019] R. Aljundi, M. Lin, B. Goujaud, and Y. Bengio.  Gradient based sample selection for online continual learning.  _Advances in neural information processing systems_ , 32, 2019.
  * Biesialska et al. [2020] M. Biesialska, K. Biesialska, and M. R. Costa-jussà.  Continual lifelong learning in natural language processing: A survey.  _arXiv preprint arXiv:2012.09823_ , 2020.
  * Caccia et al. [2020] L. Caccia, E. Belilovsky, M. Caccia, and J. Pineau.  Online learned continual compression with adaptive quantization modules.  In _International conference on machine learning_ , pages 1240–1250. PMLR, 2020.
  * Cai et al. [2022] J. Cai, X. Wang, C. Guan, Y. Tang, J. Xu, B. Zhong, and W. Zhu.  Multimodal continual graph learning with neural architecture search.  In _Proceedings of the ACM Web Conference 2022_ , pages 1292–1300, 2022.
  * Carta et al. [2021] A. Carta, A. Cossu, F. Errica, and D. Bacciu.  Catastrophic forgetting in deep graph networks: an introductory benchmark for graph classification.  _arXiv preprint arXiv:2103.11750_ , 2021.
  * Chrysakis and Moens [2020] A. Chrysakis and M.-F. Moens.  Online continual learning from imbalanced data.  In _International Conference on Machine Learning_ , pages 1952–1961. PMLR, 2020.
  * Daruna et al. [2021] A. Daruna, M. Gupta, M. Sridharan, and S. Chernova.  Continual learning of knowledge graph embeddings.  _IEEE Robotics and Automation Letters_ , 6(2):1128–1135, 2021.
  * Delange et al. [2021] M. Delange, R. Aljundi, M. Masana, S. Parisot, X. Jia, A. Leonardis, G. Slabaugh, and T. Tuytelaars.  A continual learning survey: Defying forgetting in classification tasks.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2021.
  * Farajtabar et al. [2020] M. Farajtabar, N. Azizan, A. Mott, and A. Li.  Orthogonal gradient descent for continual learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3762–3773. PMLR, 2020.
  * Gretton et al. [2009] A. Gretton, A. Smola, J. Huang, M. Schmittfull, K. Borgwardt, and B. Schölkopf.  Covariate shift by kernel mean matching.  _Dataset shift in machine learning_ , 3(4):5, 2009\.
  * Hamilton et al. [2018] W. L. Hamilton, R. Ying, and J. Leskovec.  Inductive representation learning on large graphs, 2018.
  * Hochbaum [1996] D. S. Hochbaum.  Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems.  In _Approximation algorithms for NP-hard problems_ , pages 94–143. 1996.
  * Jung et al. [2016] H. Jung, J. Ju, M. Jung, and J. Kim.  Less-forgetting learning in deep neural networks.  _arXiv preprint arXiv:1607.00122_ , 2016.
  * Kazemi et al. [2020] S. M. Kazemi, R. Goel, K. Jain, I. Kobyzev, A. Sethi, P. Forsyth, and P. Poupart.  Representation learning for dynamic graphs: A survey.  _J. Mach. Learn. Res._ , 21(70):1–73, 2020.
  * Kipf and Welling [2017] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks, 2017\.
  * Kirkpatrick et al. [2017] J. Kirkpatrick, R. Pascanu, N. Rabinowitz, J. Veness, G. Desjardins, A. A. Rusu, K. Milan, J. Quan, T. Ramalho, A. Grabska-Barwinska, et al.  Overcoming catastrophic forgetting in neural networks.  _Proceedings of the national academy of sciences_ , 114(13):3521–3526, 2017.
  * Knoblauch et al. [2020] J. Knoblauch, H. Husain, and T. Diethe.  Optimal continual learning has perfect memory and is np-hard.  In _International Conference on Machine Learning_ , pages 5327–5337. PMLR, 2020.
  * Kou et al. [2020] X. Kou, Y. Lin, S. Liu, P. Li, J. Zhou, and Y. Zhang.  Disentangle-based continual graph representation learning.  _arXiv preprint arXiv:2010.02565_ , 2020.
  * Kumaran et al. [2016] D. Kumaran, D. Hassabis, and J. L. McClelland.  What learning systems do intelligent agents need? complementary learning systems theory updated.  _Trends in cognitive sciences_ , 20(7):512–534, 2016.
  * Li et al. [2018] Q. Li, Z. Han, and X.-M. Wu.  Deeper insights into graph convolutional networks for semi-supervised learning.  In _Thirty-Second AAAI conference on artificial intelligence_ , 2018\.
  * Li and Hoiem [2017] Z. Li and D. Hoiem.  Learning without forgetting.  _IEEE transactions on pattern analysis and machine intelligence_ , 40(12):2935–2947, 2017.
  * Liu et al. [2021] H. Liu, Y. Yang, and X. Wang.  Overcoming catastrophic forgetting in graph neural networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 8653–8661, 2021.
  * Lopez-Paz and Ranzato [2017] D. Lopez-Paz and M. Ranzato.  Gradient episodic memory for continual learning.  _Advances in neural information processing systems_ , 30, 2017.
  * Ma et al. [2021] J. Ma, J. Deng, and Q. Mei.  Subgroup generalization and fairness of graph neural networks, 2021.
  * McClelland et al. [1995] J. L. McClelland, B. L. McNaughton, and R. C. O’Reilly.  Why there are complementary learning systems in the hippocampus and neocortex: insights from the successes and failures of connectionist models of learning and memory.  _Psychological review_ , 102(3), 1995.
  * McCloskey and Cohen [1989] M. McCloskey and N. J. Cohen.  Catastrophic interference in connectionist networks: The sequential learning problem.  In _Psychology of learning and motivation_ , volume 24, pages 109–165. Elsevier, 1989.
  * Parisi et al. [2019] G. I. Parisi, R. Kemker, J. L. Part, C. Kanan, and S. Wermter.  Continual lifelong learning with neural networks: A review.  _Neural Networks_ , 113:54–71, 2019.
  * Rolnick et al. [2018] D. Rolnick, A. Ahuja, J. Schwarz, T. P. Lillicrap, and G. Wayne.  Experience replay for continual learning.  _arXiv preprint arXiv:1811.11682_ , 2018.
  * Rusu et al. [2016] A. A. Rusu, N. C. Rabinowitz, G. Desjardins, H. Soyer, J. Kirkpatrick, K. Kavukcuoglu, R. Pascanu, and R. Hadsell.  Progressive neural networks.  _arXiv preprint arXiv:1606.04671_ , 2016.
  * Saha et al. [2021] G. Saha, I. Garg, and K. Roy.  Gradient projection memory for continual learning.  _arXiv preprint arXiv:2103.09762_ , 2021.
  * Shin et al. [2017] H. Shin, J. K. Lee, J. Kim, and J. Kim.  Continual learning with deep generative replay.  _Advances in neural information processing systems_ , 30, 2017.
  * Veličković et al. [2017] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Wang et al. [2020] C. Wang, Y. Qiu, and S. Scherer.  Bridging graph network to lifelong learning with feature interaction.  2020\.
  * Wang et al. [2022] C. Wang, Y. Qiu, D. Gao, and S. Scherer.  Lifelong graph learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 13719–13728, 2022.
  * Wang et al. [2019] M. Wang, D. Zheng, Z. Ye, Q. Gan, M. Li, X. Song, J. Zhou, C. Ma, L. Yu, Y. Gai, et al.  Deep graph library: A graph-centric, highly-performant package for graph neural networks.  _arXiv preprint arXiv:1909.01315_ , 2019.
  * Wortsman et al. [2020] M. Wortsman, V. Ramanujan, R. Liu, A. Kembhavi, M. Rastegari, J. Yosinski, and A. Farhadi.  Supermasks in superposition.  _Advances in Neural Information Processing Systems_ , 33:15173–15184, 2020.
  * Wu et al. [2019] Y. Wu, Y. Chen, L. Wang, Y. Ye, Z. Liu, Y. Guo, and Y. Fu.  Large scale incremental learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 374–382, 2019.
  * Xu et al. [2020] Y. Xu, Y. Zhang, W. Guo, H. Guo, R. Tang, and M. Coates.  Graphsail: Graph structure aware incremental learning for recommender systems.  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, pages 2861–2868, 2020.
  * Yoon et al. [2017] J. Yoon, E. Yang, J. Lee, and S. J. Hwang.  Lifelong learning with dynamically expandable networks.  _arXiv preprint arXiv:1708.01547_ , 2017.
  * Yoon et al. [2019] J. Yoon, S. Kim, E. Yang, and S. J. Hwang.  Scalable and order-robust continual learning with additive parameter decomposition.  _arXiv preprint arXiv:1902.09432_ , 2019.
  * Zhang et al. [2021] X. Zhang, D. Song, and D. Tao.  Hierarchical prototype networks for continual graph representation learning.  _arXiv preprint arXiv:2111.15422_ , 2021.
  * Zhang et al. [2022] X. Zhang, D. Song, and D. Tao.  Cglb: Benchmark tasks for continual graph learning.  In _Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track_ , 2022.
  * Zhou and Cao [2021a] F. Zhou and C. Cao.  Overcoming catastrophic forgetting in graph neural networks with experience replay.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 4714–4722, 2021a.
  * Zhou and Cao [2021b] F. Zhou and C. Cao.  Overcoming catastrophic forgetting in graph neural networks with experience replay.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 4714–4722, 2021b.
  * Zhu et al. [2020] J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra.  Beyond homophily in graph neural networks: Current limitations and effective designs.  _arXiv preprint arXiv:2006.11468_ , 2020.
  * Zhu et al. [2021] Q. Zhu, N. Ponomareva, J. Han, and B. Perozzi.  Shift-robust gnns: Overcoming the limitations of localized graph training data, 2021.

##  Appendix A Proof of Theorem 1

In this appendix, we provide proof for Theorem 1.

###### Proof.

Suppose $P_{i}\subset\mathcal{V}_{i}$ is the experience replay set selected by
solving Eq. (15). Let $s$ be the structure of interest with distance measure
$d_{s}$. Let $\mathcal{M}$ be a given GNN model with distortion $\alpha$ and
scaling factor $r$ and its prediction function $g$.

Let $\sigma:\mathcal{V}_{i}\mapsto P_{i}$ denote a mapping that map a vertex
$v$ from $\mathcal{V}_{i}$ to the closest vertex in $P_{i}$, i.e.,

$\sigma(v)=\operatorname*{arg\,min}_{u\in P_{i}}d_{s}(u,v).$ (6)

Let’s consider the loss of vertex $v$,
$\mathcal{L}(g\circ\mathcal{M}(v),y_{v})$. By assumption, $\mathcal{L}$ is
smooth and let’s denote $B_{\mathcal{L}}^{up1}$ to be the upper bound for the
first derivative with respect to $g\circ\mathcal{M}(v)$ and
$B_{\mathcal{L}}^{up2}$ to be the upper bound for the first derivative with
respect to $y_{v}$. Then, consider the Taylor expansion of
$\mathcal{L}(g\circ\mathcal{M}(v),y_{v})$ with respect to $\sigma(v)$, which
is given as follows

$\begin{split}\mathcal{L}(g\circ\mathcal{M}(v),y_{v})&\leq\mathcal{L}(g\circ\mathcal{M}(\sigma(v)),y_{\sigma(v)})+\\\
&B_{\mathcal{L}}^{up1}||g\circ\mathcal{M}(v)-g\circ\mathcal{M}(\sigma(v))||\\\
&+B_{\mathcal{L}}^{up2}||y_{v}-y_{\sigma(v)}||\end{split}$ (7)

Next, let’s examine the inequality above term by term and start with
$||g\circ\mathcal{M}(v)-g\circ\mathcal{M}(\sigma(v))||$. Let’s denote $h_{v}$
and $h_{\sigma(v)}$ the embedding for vertex $v$ and $\sigma(v)$. Then, we
have that,

$||g\circ\mathcal{M}(v)-g\circ\mathcal{M}(\sigma(v))||=||g(h_{v})-g(h_{\sigma(v)})||$
(8)

By definition of distortion as given in Def. 2, we have that,

$||h_{v}-h_{\sigma(v)}||\leq r\alpha d_{s}(v,\sigma(v))$ (9)

By assumption, the prediction function $g$ is smooth. Let $B_{g}$ denote the
upper bound of first derivative of the prediction function $g$. Then, we have

$||g(h_{v})-g(h_{\sigma(v)})||\leq B_{g}^{up}||h_{v}-h_{\sigma(v)}||$ (10)

Substitute all these back, we have

$||g\circ\mathcal{M}(v)-g\circ\mathcal{M}(\sigma(v))||\leq B_{g}^{up}r\alpha
d_{s}(v,\sigma(v))$ (11)

Next, let’s consider $||y_{v}-y_{\sigma(v)}||$. Similarly, by the data
smoothness assumption and distortion, we have that

$||y_{v}-y_{\sigma(v)}||\leq B_{l}||h_{v}-h_{\sigma(v)}||\leq
B_{l}^{up}r\alpha d_{s}(v,\sigma(v))$ (12)

Substitute these back to the inequality we start with, we have that

$\begin{split}&\mathcal{L}(g\circ\mathcal{M}(v),y_{v})\leq\mathcal{L}(g\circ\mathcal{M}(\sigma(v)),y_{\sigma(v)})+\\\
&\quad B_{\mathcal{L}}^{up1}B_{g}^{up}r\alpha
d_{s}(v,\sigma(v))+B_{\mathcal{L}}^{up2}B_{l}^{up}r\alpha
d_{s}(v,\sigma(v))\\\
&\leq\mathcal{L}(g\circ\mathcal{M}(\sigma(v)),y_{\sigma(v)})+\\\
&(B_{l}^{up}B_{\mathcal{L}}^{up1}+B_{g}^{up}B_{\mathcal{L}}^{up2})r\alpha\max_{v^{\prime}\in\mathcal{V}_{i}}d_{s}(v^{\prime},\sigma(v^{\prime}))\\\
&=\mathcal{L}(g\circ\mathcal{M}(\sigma(v)),y_{\sigma(v)})+\\\
&(B_{l}^{up}B_{\mathcal{L}}^{up1}+B_{g}^{l}B_{\mathcal{L}}^{up2})r\alpha
D_{s}(\mathcal{V}_{i},P_{i}).\end{split}$ (13)

Since the inequality above holds for every vertex $v$, then we have

$\begin{split}R^{\mathcal{L}}(g\circ\mathcal{M},\mathcal{V}_{i})&\leq
R^{\mathcal{L}}(g\circ\mathcal{M},P_{i})+\\\
&(B_{l}^{up}B_{\mathcal{L}}^{up1}+B_{g}^{up}B_{\mathcal{L}}^{up2})r\alpha
D_{s}(\mathcal{V}_{i},P_{i})\\\
&=R^{\mathcal{L}}(g\circ\mathcal{M},P_{i})+\mathcal{O}(\alpha
D_{s}(\mathcal{V}_{i},P_{i}))\end{split}$ (14)

∎

##  Appendix B Procedure for Solving Eq. 15

First recall that the optimization we want to solve is as follows.

$\begin{split}\min_{P_{j}\subset\mathcal{V}_{j}}\max_{u\in\mathcal{V}_{j}\backslash
P_{j}}\min_{v\in P_{j}}d_{\text{spd}}(u,v)\quad s.t.|P_{j}|=b.\end{split}$
(15)

$d_{\text{spd}}(.)$ is the shortest path distance and $b$ is the number of
samples (experience) to select from each task. Eq. 15 amounts to the well-
known k-center problem [13] in graph theory and is NP-hard. For our
experiment, we use Eq. 15 as guidance and modify the simple greedy algorithm,
farthest-first traversal, to be a sampling method for obtaining replay samples
for a given task. We now describe how we modified the standard greedy
algorithm into a sampling algorithm. We start with describing the standard
greedy algorithm.

Algorithm 2 k-center Greedy

0: $\mathcal{V}$ //vertex set of a given graph

0: $b$ //number of centersInitialize an empty array $V$

  1. 1.

randomly picks a random vertex $v$ to $V$

  2. 2.

pick the next vertex to be the vertex furthest away from $V$

  3. 3.

repeat until $|V|=b$

The procedure described above is a standard 2-approximation greedy algorithm
for k-center problem. Next, we describe its sampling variant which use the
distance as the chance of being sampled.

Algorithm 3 Sampling for Experience Buffer

0: $\mathcal{V}_{i}$ //vertex set of a given graph

0: $\mathcal{G}$ //latest graph

0: $b$ //size of set to be sampledSample/select the set of size $b$ with the
following procedures:

  1. 1.

initialize $P_{i}$ with the vertex of the highest degree.

  2. 2.

sample $u$ from $\mathcal{V}_{i}\backslash P_{i}$ based on probability $p_{u}$
proportion to $D_{s}(u,\mathcal{V}_{i}\backslash P_{i})=\min_{v\in
P_{i}}d_{s}(u,v)$, following the formula,

$p_{u}=\frac{D_{s}(u,P_{i})}{\sum_{v\in\mathcal{V}_{i}\backslash
P_{i}}D_{s}(v,P_{i})}$

  3. 3.

repeat until $b$ vertices are sampled

###  B.1 Running Time Complexity

It is obvious that the procedure above runs in $\mathcal{O}(k)$ if the
distance between any pair of vertices is given and runs in $\mathcal{O}(kn)$
if the distance needed to be computed for each step, where $n$ is the number
of vertice of the given task.

##  Appendix C Additional Experimental Details

In this appendix, we provide additional experimental results and include a
detailed set-up of the experiments for reproducibility.

###  C.1 Task Incremental Learning Setting

We provide additional details on how we create the task incremental learning
setting for each dataset and conduct the training. As we discussed in Sec. 6,
we follow closely the setting used in [44] and evenly divide the dataset into
k-way classification task. The difference between our setting and [44] is that
we gradually grow the graph structure with the data from each task. Suppose
the division for the Cora dataset is: Task 0: binary classification between
class 0 and 1, Task 1: binary classification between class 2 and 3, and Task
2: classification between class 4, 5 and 6. Then, at stage 0 (Task 0), the
system only has access to the graph structure induced by vertices from class 0
and 1, i.e., if there are vertices from other tasks that are in the
neighborhood of the vertices of class 0 & 1\. These vertices won’t be
seen/accessed by the system. This mimics the evolving graph setting in real-
life. We provide a graphical illustration on the difference between the task
increment learning in constant graph and evolving graph in Fig. 8.

Table 3: Dataset, Task and GNN Details  Dataset | Cora | CoauthorCS | Reddit
---|---|---|---
$\\#$ Vertexes | 2,708 | 18,333 | 232,965
$\\#$ Edges | 10,556 | 327,576 | 114,615,892
$\\#$ dim. of Node Features | 1,433 | 6,805 | 602
$\\#$ Classes | 7 | 15 | 41
$\\#$ Tasks | 3 | 5 | 8
$\\#$ Classes per Task | 2/3 | 3 | 5/6
$\\#$ GNN Hidden Units | 32 | 128 | 256
Optimizer | Adam
Learning Rate | 0.01
Weight Decay | 0.0005
Dropout | 0
Epoch | 100

###  C.2 Incremental Training Procedure

Suppose $\mathcal{T}_{1},\mathcal{T}_{2},...\mathcal{T}_{m}$ is the set of
classification tasks created from the dataset. Then, the standard incremental
training procedure is given in Alg. 4 and a graphical illustration is given in
Fig. 7.

###  C.3 Hyperparameter

We provide addtional experiment on exploring the size of experience replay
buffer used in the experiment. The result is illustrated in Fig. 6. In Fig. 6,
the x-axis is the size of the experience buffer with respect to the size of
the training set from each task and y-axis is the measure for catastrophic
forgetting (the lower, the better). We can see from Fig. 6, the performance of
the system increase as we increase the replay set size, as per our intuition.
The interesting part is that, experience replay is effective or has the most
significant drop in 1% or 5%, which only cost a small fract when comparing to
full replay.

Figure 6: Performance of the system with respect to the size of experience
buffer.  Algorithm 4 Incremental Training

Input: $\mathcal{T}_{1},\mathcal{T}_{2},...\mathcal{T}_{m}$ //classification
task created from the dataset. For $\tau$ in
$\mathcal{T}_{1},\mathcal{T}_{2},...\mathcal{T}_{m}$:

  1. 1.

update/grow the graph structure with data from $\tau$

  2. 2.

obtain $D^{tr}$ from $\tau$

  3. 3.

train the existing GNN model and a new task prediction head on $D^{tr}$

  4. 4.

if evaluation, evaluate the model on the current and previous task

Figure 7: Incremental Training in Development Phase. The figure above
illustrates what task data the model use for training and evaluation.  Figure
8: Difference between Inductive GIL and Transductive GIL. As illustrated in
the top half of the figure, in the evolving graph setting, the appearing tasks
expand/change the existing graph structure, resulting in changes in the
neighborhood (input to the GNN) of some previous vertices. As discussed in the
main body of the paper, this structural changes/dependency would cause
distribution shift in the previously learnt information of the model. On the
other hand, in the constant graph setting, because the complete graph
structure is available from te very first beginning. The neighborhoods of all
the vertices are static/stay unchanged throughout different learning stages.
Therefore, structural dependency is an unique challenge in the incremental
learning in evolving graph.


# A New LBV Candidate in M33

John C. Martin University of Illinois Springfield  Roberta M. Humphreys
University of Minnesota  Kerstin Weis Astronomical Institute, Faculty for
Physics and Astronomy, Ruhr University Bochum  Dominik J. Bomans Astronomical
Institute, Faculty for Physics and Astronomy, Ruhr University Bochum

(Accepted May 15, 2023)

###### Abstract

The evolutionary relationships and mechanisms governing the behavior of the
wide variety of luminous stars populating the upper H-R diagram are not well
established. Luminous blue variables (LBVs) are particularly rare, with only a
few dozen identified in the Milky Way and nearby galaxies. Since 2012, the
Barber Observatory Luminous Stars Survey has monitored more than 100 luminous
targets in M33, including M33C-4119 which has recently undergone photometric
and spectroscopic changes consistent with an S Doradus eruption of an LBV.

Massive stars(732),Luminous blue variable stars(944),Triangulum Galaxy(1712)

## 1

M33C-4119 (LGGS J013312.81+303012.6) is a new Luminous Blue Variable (LBV)
candidate discovered in an on-going survey of M33 (Martin & Humphreys, 2017).
LBVs are rare and difficult to identify due to the infrequency of their
characteristic photometric and spectroscopic variability. Only a few dozen
have been identified in the Milky Way and nearby galaxies (Humphreys et al.,
2016). Their eruptive mechanism and connection to other classes of massive
stars including B[e] supergiants, warm hypergiants, and supernova impostors
are poorly understood.

M33C-4119 is a luminous OB-supergiant (Humphreys et al., 2014) in an outer
spiral arm of M33 numbered B78 in Association 127 (Humphreys & Sandage, 1980)
about 12 arc minutes southwest of the galaxy center. The designation M33C-4119
is from Burggraf (2015). It is also identified as IFM_B 333 by Ivanov et al.
(1993) and J013312.81+303012.6 by Massey et al. (2016). Before 2012 it
exhibited 0.1 – 0.2 mag alpha-Cygni type variations (Hartman et al., 2006;
Chambers et al., 2016; Burggraf, 2015) including measurements of digitized
photographic plates as far back as 1968 (Gottschling, 2017). A few
measurements $\sim$0.5 mag brighter than average were recorded 2001–2002
(Burggraf, 2015; Massey et al., 2016).

From 2012 to the present its brightness has been recorded several times a year
by a BVRI CCD survey of M33 conducted with the University of Illinois
Springfield Barber Observatory 20-inch telescope(Martin & Humphreys, 2017).
From 2012 – 2018 it brightened $\approx$ 1.0 mag in all observed bands,
including a rapid rise beginning in 2017. The initial stage, 2012–2016, is
confirmed by CCD photometry recorded by the Tautenburg Landessterwarte 2-m
telescope (Burggraf, 2015; Gottschling, 2017). It maintained peak brightness
($\approx$ 0.5 magnitude brighter than seen previously) for more than a year
before a more rapid decline to its minimum brightness by 2021 (Figure 1 and
Table 1). Throughout the event the star’s color was correlated with its change
in brightness as expected during an S Doradus eruption, being significantly
bluer/hotter when fainter and redder/cooler when visually brighter.

Spectra of M33C-4119 were obtained with the MMT Hectospec Multi-Object
Spectrograph in 2010.76 and 2014.88 with the 600-line grating in the blue and
red covering 3600 to 8300A (Figure 2 and 3) and also with the LBT MODS
spectrograph on 2011.75 (Humphreys et al., 2013, 2014, 2017). The 2010 and
2011 spectra closely resemble each other. The 2014 spectrum shows a
significant change and a shift to a cooler apparent temperature. A fourth
spectrum recorded in 2007.76 by Burggraf (2015) using the CAFOS spectrograph
on the Calar Alto 2.2-m telescope is similar in appearance to the 2010 and
2011 spectra with lower resolution and a higher noise level which affects the
clear detection of weaker emission and absorption features.

Both the 2007 and 2010 spectra show a hot supergiant with a stellar wind and
mass loss. The H$\alpha$ and H$\beta$ emission lines have prominent electron
scattering wings in both spectra, and in the 2010 spectrum P Cygni absorption
minima are present at H$\beta$ and H$\gamma$. In both 2007 and 2010, strong He
I emission is present at $\lambda$ 5876, 6678 and 7065. In the 2010 spectrum
other He I lines are present in absorption. Strong absorption lines of Si III,
N II and O II are present along with a weak Mg II $\lambda$ 4481 line. The
absorption lines suggest an early B-type supergiant of spectral type B2 – B3
when the star was at minimum brightness.

In 2014 when the star was halfway through its period of brightening, the He I
emission lines are replaced by absorption and the He I lines previously
present in absorption are weaker. Absorption lines of Ca II K, the Na I D
lines and Mg II are significantly stronger, indicating a shift to cooler
temperatures consistent with a late B-type spectral type ($\approx$ B8).

To estimate the star’s total bolometric luminosity and place on an HR Diagram,
we determined the visual extinction. Since M33C-4119 has strong emission
lines, we adopt $A_{V}=1.10$ from two nearby OB stars. Although we lack a
spectrum at maximum light, we argue that the observed shift in color supports
an equivalent late A or F spectral type with little or no bolometric
correction. A maximum V $\approx$ 16.8 mag at a distance modulus of 24.5 mag
(Scowcroft et al., 2009) implies M${}_{v}=M_{bol}\approx$ -8.8 (Figure 4. This
is also consistent with the luminosity estimated from the spectral types and
brightness observed in 2010 and 2014.

LBVs are defined by S Doradus eruptive episodes characterized by a 1-2 mag
increase in visual brightness accompanied by an apparent shift to cooler
temperatures and change in spectral type to late-A to F type with little or no
appreciable change in luminosity. Many hot supergiants have emission lines and
the B[e] supergiants are spectroscopically like LBVs, thus observing an S Dor
event is the only way to confirm a star is an LBV. The brightening of
M33C-4119 is consistent with an S Dor eruption including the time scale, the
rise in visual brightness, the reddening of the colors near peak brightness,
and the shift to later spectral type during the brightening. Although there is
no spectrum at maximum, the case is compelling that M33C-4119 is an LBV.

Figure 1: The V magnitude and colors of M33C-4119 (LGGS J013312.81+303012.7).
The triangles are the LGGS (Massey et al., 2016). The open squares with error
bars are Burggraf (2015) and Gottschling (2017) CCD photometry from the
Tautenburg Landessterwarte 2-m telescope. The crosses are PanSTARRS Sloan g
(Chambers et al., 2016). The filled circles with error bars are Martin &
Humphreys (2017) and this work. The dashed horizontal lines in the color plots
note the average value. The dashed vertical lines mark the times of the
spectra recorded in 2010 and 2014.  Table 1: Recent Photometry of M33C-4119

MJD | V | (B-V) | (V-I)
---|---|---|---
56140.40 | $17.84\pm 0.06$ |  |
56599.22 | $17.71\pm 0.07$ | $0.03\pm 0.09$ |
57035.14 | $17.42\pm 0.04$ | $0.15\pm 0.06$ |
57310.16 | $17.28\pm 0.05$ | $0.11\pm 0.06$ |
57406.10 | $17.26\pm 0.05$ | $0.35\pm 0.07$ | $0.35\pm 0.09$
57634.41 | $17.31\pm 0.07$ | $0.04\pm 0.11$ |
57638.40 | $17.33\pm 0.05$ | $0.11\pm 0.06$ | $0.34\pm 0.10$
57964.40 | $17.57\pm 0.04$ |  | $0.21\pm 0.09$
57988.43 | $17.31\pm 0.06$ |  |
58043.15 | $17.16\pm 0.04$ | $0.15\pm 0.06$ | $0.38\pm 0.10$
58073.22 | $17.28\pm 0.05$ | $0.00\pm 0.16$ |
58108.13 | $17.44\pm 0.05$ | $0.12\pm 0.06$ | $0.29\pm 0.09$
58316.35 | $17.18\pm 0.04$ | $0.20\pm 0.06$ |
58339.40 | $16.97\pm 0.05$ | $0.14\pm 0.08$ |
58373.15 | $16.99\pm 0.06$ | $0.26\pm 0.08$ |
58375.16 | $16.88\pm 0.04$ |  | $0.44\pm 0.10$
58433.02 | $16.87\pm 0.05$ |  | $0.32\pm 0.11$
58673.38 | $16.86\pm 0.03$ | $0.28\pm 0.04$ |
58695.39 | $17.00\pm 0.04$ |  |
58696.41 | $17.02\pm 0.05$ | $0.14\pm 0.09$ |
58750.20 | $16.87\pm 0.04$ | $0.23\pm 0.05$ | $0.40\pm 0.09$
58757.17 | $16.86\pm 0.05$ |  |
58779.18 | $16.81\pm 0.04$ | $0.21\pm 0.05$ |
58784.14 | $16.86\pm 0.04$ |  | $0.50\pm 0.09$
58812.20 | $16.87\pm 0.06$ |  |
59059.40 | $17.14\pm 0.06$ |  | $0.40\pm 0.10$
59081.34 | $17.19\pm 0.05$ | $0.13\pm 0.06$ | $0.42\pm 0.09$
59082.38 | $17.22\pm 0.05$ | $0.16\pm 0.06$ |
59161.14 | $17.36\pm 0.04$ |  | $0.38\pm 0.10$
59171.15 | $17.34\pm 0.05$ | $0.09\pm 0.08$ | $0.37\pm 0.09$
59227.14 | $17.55\pm 0.05$ | $0.09\pm 0.07$ | $0.31\pm 0.09$
59415.39 | $17.81\pm 0.07$ |  |
59441.42 | $17.78\pm 0.06$ |  |
59442.41 | $17.80\pm 0.05$ |  |
59463.33 | $17.76\pm 0.06$ | $0.06\pm 0.08$ | $0.14\pm 0.10$
59522.13 | $17.63\pm 0.05$ |  | $0.09\pm 0.10$
59525.12 | $17.65\pm 0.05$ |  |
59546.20 | $17.59\pm 0.05$ | $0.10\pm 0.06$ | $0.33\pm 0.09$
59551.14 | $17.61\pm 0.06$ |  | $0.07\pm 0.11$
59583.20 | $17.59\pm 0.04$ |  |
59608.14 | $17.61\pm 0.05$ | $0.07\pm 0.09$ |

Note. — From survey of luminous stars in M33 described in Martin & Humphreys
(2017).

Figure 2: The spectrum of M33C-4119 (LGGS J013312.81+303012.7) recorded using
the blue channel of the 600-line grating of the MMT Hectospec Multi-Object
Spectrograph in 2010.76 and 2014.88.  Figure 3: The spectrum of M33C-4119
(LGGS J013312.81+303012.7) recorded using the red channel of the 600-line
grating of the MMT Hectospec Multi-Object Spectrograph in 2010.76 and 2014.88.
Figure 4: An HRD for M31 and M33 reproduced from Humphreys et al. (2016)
showing the location of M33C-4119 (LGGS J013312.81+303012.7).

The UIS Barber Observatory survey of luminous stars in M33 was initiated under
and supported by NSF grant AST-1108890 with additional support from the
University of Illinois Springfield Henry R. Barber Astronomy Endowment funded
by the people of Central Illinois. We also thank Brigita Burggraf and Niels
Gottschling for the photometry and spectroscopy they contributed. This work
also made use of the Pan-STARRS1 Surveys (PS1) and the PS1 public science
archive which has been made possible through contributions of a number of
organizations credited in Chambers et al. (2016).

## References

  * Burggraf (2015) Burggraf, B. 2015, PhD thesis, Ruhr University, Bochum, Germany
  * Chambers et al. (2016) Chambers, K. C., Magnier, E. A., Metcalfe, N., et al. 2016, arXiv e-prints, arXiv:1612.05560, doi: 10.48550/arXiv.1612.05560
  * Gottschling (2017) Gottschling, N. 2017, Master’s thesis, Ruhr University, Bochum, Germany
  * Hartman et al. (2006) Hartman, J. D., Bersier, D., Stanek, K. Z., et al. 2006, MNRAS, 371, 1405, doi: 10.1111/j.1365-2966.2006.10764.x
  * Humphreys et al. (2013) Humphreys, R. M., Davidson, K., Grammer, S., et al. 2013, ApJ, 773, 46, doi: 10.1088/0004-637X/773/1/46
  * Humphreys et al. (2017) Humphreys, R. M., Davidson, K., Hahn, D., Martin, J. C., & Weis, K. 2017, ApJ, 844, 40, doi: 10.3847/1538-4357/aa7cef
  * Humphreys & Sandage (1980) Humphreys, R. M., & Sandage, A. 1980, ApJS, 44, 319, doi: 10.1086/190696
  * Humphreys et al. (2014) Humphreys, R. M., Weis, K., Davidson, K., Bomans, D. J., & Burggraf, B. 2014, ApJ, 790, 48, doi: 10.1088/0004-637X/790/1/48
  * Humphreys et al. (2016) Humphreys, R. M., Weis, K., Davidson, K., & Gordon, M. S. 2016, ApJ, 825, 64, doi: 10.3847/0004-637X/825/1/64
  * Ivanov et al. (1993) Ivanov, G. R., Freedman, W. L., & Madore, B. F. 1993, ApJS, 89, 85, doi: 10.1086/191840
  * Martin & Humphreys (2017) Martin, J. C., & Humphreys, R. M. 2017, AJ, 154, 81, doi: 10.3847/1538-3881/aa7e2e
  * Massey et al. (2016) Massey, P., Neugent, K. F., & Smart, B. M. 2016, AJ, 152, 62, doi: 10.3847/0004-6256/152/3/62
  * Scowcroft et al. (2009) Scowcroft, V., Bersier, D., Mould, J. R., & Wood, P. R. 2009, MNRAS, 396, 1287, doi: 10.1111/j.1365-2966.2009.14822.x


# Self-supervised Point Cloud Completion on Real Traffic Scenes via Scene-
concerned Bottom-up Mechanism

##  1 Abstract

Real scans always miss partial geometries of objects due to the self-
occlusions, external-occlusions, and limited sensor resolutions. Point cloud
completion aims to refer the complete shapes for incomplete 3D scans of
objects. Current deep learning-based approaches rely on large-scale complete
shapes in the training process, which are usually obtained from synthetic
datasets. It is not applicable for real-world scans due to the domain gap. In
this paper, we propose a self-supervised point cloud completion method
(TraPCC) for vehicles in real traffic scenes without any complete data. Based
on the symmetry and similarity of vehicles, we make use of consecutive point
cloud frames to construct vehicle memory bank as reference. We design a
bottom-up mechanism to focus on both local geometry details and global shape
features of inputs. In addition, we design a scene-graph in the network to pay
attention to the missing parts by the aid of neighboring vehicles. Experiments
show that TraPCC achieve good performance for real-scan completion on KITTI
and nuScenes traffic datasets even without any complete data in training. We
also show a downstream application of 3D detection, which benefits from our
completion approach.

††$\dagger$: Corresponding author.

##  2 Introduction

Using scan sensors, such as RGBD cameras or LiDARs, to capture the point cloud
of objects or scenes becomes an important mean to obtain the real-world
information [1, 2]. However, in real applications, like autonomous driving, it
is unpractical to scan the traffic scenes from different views to acquire
complete shapes of vehicles. Almost all objects have incomplete point clouds
due to the self-occlusion, external-occlusion, and limited sensor resolution.
Complementing the missing geometries of point cloud is significant for many
downstream tasks [3, 4], including scene understanding, navigation, etc.

Previous approaches [5, 6, 5, 7, 8, 9] of point cloud completion are in
supervised manner, which heavily rely on ground truth for training the neural
network. They utilize synthetic CAD models from ShapeNet [10] to create a
large-scale dataset containing pairs of partial and complete point clouds.
However, for real scans, it is difficult to access high-quality paired
training data. Some recent works [11, 12, 13, 14] tend to learn a completion
network by an unpaired way, which focus on establishing the shape
correspondence in latent space between the incomplete point clouds and
complete ones. However, such methods still need abundant synthetic complete
data in the training process. The gap between synthetic data and real scans
and limited training samples of objects make such methods difficult to be
extended to real applications. For autonomous driving, LiDAR is the widely-
used sensor to capture point clouds of traffic scenes. Due to the working
principles of LiDAR, the point cloud has its own characteristics, like the
ring sweeps, the varying sparsity, etc. It is more challenging to use
synthetic data to solve the LiDAR point cloud completion. Diverse vehicle
shapes in the real world is also a thorny problem for above methods.

Fig. 1: (Left) Raw LiDAR scan from KITTI and (Right) completion results by
TraPCC. We attach several images of corresponding cars for reference. It shows
that our method can achieve reasonable predictions even for extremely sparse
partial vehicle point cloud and approach referred ground truth shown in the
images.

Actually, without seeing one object in 360 degree, human can still imagine the
whole appearance of the object based on the partial information and the memory
of similar objects. For vehicles in captured traffic scenes, we only have
their partial point cloud from one view. But we have large-scale partial point
clouds of other vehicles from other views. In addition, we capture the traffic
scene consecutively, the temporal information is also helpful for
strengthening the memory. Motivated by these findings, we propose a self-
supervised approach (TraPCC) for point cloud completion on real traffic scans
via utilizing the similarity and symmetry of vehicles. To focus on the local
geometries and global shape and size features of the input partial point
cloud, we design a bottom-up mechanism by forecasting dense point clouds for
the partial bodies at first and then predicting the complete point cloud based
on these results provided by the first stage. In one scene, neighboring
vehicles can guidance the prediction from two aspects, where one is that they
locates in the same view of LiDAR, so they have similar missing parts due to
the self-occlusion; the other is that they may occlude for each other.
Considering that these hints can help the network pay attention to the missing
regions of the point clouds, we propose a scene graph to mine this
characteristic, thus improving the capacity of TraPCC. We evaluate our method
on KITTI [15] tracking dataset and nuScenes [16] dataset. As Figure. 1 shows,
our method can achieve reasonable completion results for all the vehicles
detected in the scene. Because there is no paired ground truth for strict
quantitative analysis, we use alternative metrics [17] to illustrate the
fidelity and the effectiveness of our method. Ablation study denotes the
effectiveness of each module of our network. Experiments also show that TraPCC
can act as a filter and benefit the downstream 3D detection task. Our
contribution can be concluded as follows.

  1. 1)

We propose a self-supervised point cloud completion for vehicles in traffic
scenes without any complete vehicle models, which is applicable for real
scans.

  2. 2)

We design a bottom-up mechanism to focus on the missing parts from local and
global aspects to boost the completion performance.

  3. 3)

We propose scene graph in our network to make use of the guidance from
neighboring vehicles.

  4. 4)

Our method achieve good performance on real scan datasets and can benefit 3D
detection tasks for autonomous driving.

##  3 Related Work

3D shape completion has aroused a wide concern [6, 9] in recent years. We
first review related traditional methods, and then introduce deep learning-
based methods, which is categorized into supervised and unpaired approaches.

#### Traditional Methods

Early works can be divided into two categories, including geometry-based
methods and alignment-based methods. The former [18, 19, 20, 21], utilizes
geometry cues of the partial input to fill holes in the incomplete scans, and
the latter [22, 23, 24] usually retrieves complete shapes from a large
database by optimization. These traditional methods requires expensive
computation during inference and are sensitive to noise, which is not
applicable for the incomplete data captured from the real world.

#### Supervised Methods

Deep learning-based methods [5] take advantage of the neural networks to
extract features from the incomplete input shape and predict complete
representation. Point cloud-based shape completion [17] has rapid development
compared with meshes and voxel grids. Many methods [6, 5, 7, 8, 9, 25] achieve
impressive predicted results. To preserve the spatial arrangements of the
input, PF-Net [26] only predicts the missing part of the point cloud rather
than the whole object. SK-PCN [27] maps the partial scan to complete surface
with the aid of meso-skeleton. RL-GAN-Net [28] proposes a reinforcement
learning agent controlled GAN for completion and PoinTr [29] adopts a
transformer encoder-decoder architecture. These works, however, are all in
supervised manner, which requires incomplete and complete paired data for
training deep neural networks. Actually, it is not easy to access such high-
quality paired data in real-world applications. Such methods perform well for
synthetic data but not for real scans without paired ground truth.

#### Unpaired Methods

To reduce the gap between synthetically-generated data and real-world data,
some methods loose the paired data constraint in supervised methods to
unpaired data training. [30] creates a latent space created for clean and
complete data and uses an unsupervised maximum likelihood loss for the
measurement. Pcl2pcl [11] trains two separate auto-encoders for constructing
partial and complete shapes respectively, and uses GAN setup to learn a
mapping between these two latent spaces. The follow-up work [12] extends it to
multiple predictions. ShapeInversion [13] applies GAN inversion to shape
completion and achieve more faithful results. Cycle4Completion [14] designs
two cycle transformations to establish the geometric correspondence between
incomplete and complete shapes from both directions and is superior in
unpaired completion methods. Even though these methods do not reply on paired
data any more, they still use large-scale synthetic complete 3D shapes
belonging to the same kind in the training procedure. Without any complete 3D
models, our unsupervised method only takes advantage of the real scans for
point cloud completion, which is practical for real applications and has
better generalization capability.

##  4 Methodology

Fig. 2: The pipleine of TraPCC. The whole framework consists two main modules:
Whole-GT and Partial-GT generation and point cloud completion network. We
first divide the input point cloud into B(back) and F(front) two parts, then
take Partial-GT and Whole-GT as the supervision information. Neighbor features
are considered by scene graph to improve the final prediction.

###  4.1 Overview

The framework overview is illustrated in Figure. 2. The whole framework
consists of two main modules: 1) Ground truth generation. For real scans, we
cannot get real complete point cloud as ground truth in training. Based on the
similarity and symmetry properties of vehicles, we construct a memory pool to
store seen vehicles in raw point cloud as our pseudo-ground-truth database,
which will be called ground truth (GT) in the following. 2) TraPCC network. It
is in a bottom-up mechanism, which can focus on the local geometries and
global shape and size features of the input partial point cloud. Scene graph
is designed for enhancing the completion performance by considering the
guidance from neighboring objects.

Fig. 3: Ground Truth Pool in KITTI tracking dataset. It contains relative
complete real scans of vehicles with different shapes.

###  4.2 Ground Truth Generation

#### Ground Truth Pool

We extract vehicles from point cloud scenes according to 3D bounding boxes
obtained by 3D detection. For instances occur in sequential frames, they may
be captured from multiple views. We combine the point cloud in consecutive
frames according to the tracking ID and motion compensation and gain a
relative complete point cloud. We take the data with more than 1024 points as
GT candidates. Then we use the 2D contours of the three views (side, front,
and bird-eye view) of the instance to decide whether it is relative complete.
We map the point cloud to the 2D plane from one view and sample evenly along
the coordinate axis of the object coordinate system. We check the number of
points in four quadrants to judge whether the shape is evenly distributed and
then select objects with relatively evenly distributed points to the Whole-GT
pool according to the threshold by statistics. We also construct a Partial-GT
pool to store the heads and tails of vehicles in the same way. The
visualization of the GT-Pool is shown in Figure. 3.

#### Ground Truth Generation

The main steps to generate GT is illustrated in Figure 2. For objects
extracted from raw point cloud, we take the similarity of size and shape into
account to search suitable complete point cloud in GT-Pool. The shape
similarity is calculated by Chamfer Distance (CD) [31] of the input point
cloud and GT. The function of CD is

$\displaystyle d_{CD}(S_{1},S_{2})=\frac{1}{|S_{1}|}\sum_{x\in
S_{1}}\min_{y\in S_{2}}|x-y|_{2}^{2}$ (1)
$\displaystyle+\frac{1}{|S_{2}|}\sum_{y\in S_{2}}\min_{x\in
S_{1}}|y-x|_{2}^{2},$

where $S_{1}$ and $S_{2}$ denotes input point cloud and GT respectively, $x$
and $y$ represents the 3D coordinates of points. For extremely sparse input,
we modify the CD-Loss to better calculate the similarity from sparse point
cloud to dense point cloud. The modified CD-Loss (defined as MCD loss) is
shown as

$\displaystyle d_{MCD}(S_{1},S_{2})=\min(d_{CD}(S_{1},S_{2}))$ (2)
$\displaystyle=\frac{1}{S_{1}}\sum_{x\in S_{1}}\min_{y\in
S_{2}}|x-y|_{2}^{2}.$

###  4.3 Point Cloud Completion

We introduce detailed TraPCC network in this section. The main architecture is
a bottom-up point cloud completion, which take advantages of fine-grained and
global features to guide the completion of missing parts. Moreover, we design
scene graph in TraPCC to make use of the scene information from neighbours to
consider the effect of self-occlusion and external-occlusion.

To take advantage of partial and complete ground truth to extract local fine-
grained feature and global shape information respectively, we design a two-
stage completion network to get the coarse results and detailed results in
order. We use a modified PCN [17] as backbone, which uses two PointNet modules
in encoder and we discard the coarse-to-fine decoder for the reason that the
ground truth generated in original LiDAR sparse point cloud are not so dense
as synthetic models.

In the first stage (P-Net), incomplete point cloud is divided into front and
back parts according to the bounding box labeled in detection task with the
supervision of Parial-GT. And then, these two parts are stitched together as a
whole coarse object. If there is no points in the front or back parts, there
will not be a corresponding partial prediction result. The second stage
(C-Net) is designed to refine the coarse object obtained from the last stage
in order to take global shape features into consideration with the supervision
of Whole-GT.

The emitted light from LiDAR will bounce back when hitting an obstacle.
According to LiDAR working principle, 3D objects have incomplete point cloud
due to self-occlusion caused by itself and external-occlusion caused by
surrounding objects (especially the object between LiDAR and target object).
For self-occlusion cases, the instance around the target object can offer
similar partial spatial information. For external-occlusion cases, the object
nearer LiDAR can provide a clue to the occluded part of target object. We
obtain guidance through occluded information from neighbours by constructing a
scene-graph shown in Figure 2.

The scene graph is designed by taking the input data as the center of a circle
and extracting the nearest k neighbors (in experiment, we set k=3) of the
input object within a certain radius. As a result, TraPCC can effectively
optimize the prediction result with the guidance of neighbour features.

Fig. 4: TraPCC for improving detection precision. The whole process consist
three steps: (A) Detection: Using detection network to get initial detected
vehicles. (B) Point cloud completion: complete the objects extracted from the
detection stage and compute the shape difference with the original input
object to distinguish whether the point cloud is a vehicle or noise. (C)
Filter: Delete the object whose score is higher than the threshold. Green
Bounding boxes in the figure are ground truth and red ones are detection
results.

###  4.4 Loss Function

Our proposed loss function consists of three terms, the P-Net completion
CDloss between coarse partial output $Y_{coarse}$ and partial ground truth
$Y_{P-GT}$, the C-Net completion CDloss loss between detailed whole output
$Y_{detailed}$ and the whole ground truth $Y_{W-GT}$, and input-output
comparison loss (defined as MCD-Loss) between the input data$X_{input}$ and
$Y_{detailed}$.

$\displaystyle L($ $\displaystyle Y_{coarse},Y_{detailed},X_{input},Y_{gt})=$
(3) $\displaystyle d_{CD}(Y_{coarse},Y_{P-GT})+d_{CD}(Y_{detailed},Y_{W-GT})$
$\displaystyle+d_{MCD}(Y_{detailed},X_{input})$

Considering the fact that object point cloud in the real LiDAR scenes is
sparse and may miss large parts of body, MCD-Loss strengthens the connection
between the input and the output point clouds in case that the original
information will be neglected after being trained on the generated ground
truth. It can guarantee that our prediction result is not limited by generated
ground truth and keeps the characteristics of the input.

###  4.5 Adaptation for Downstream Tasks

We evaluate the effectiveness of our self-supervised point cloud completion in
detection task with the main steps illustrated in Figure. 4. Specifically, we
use 3D detection network to extract the objects from raw point cloud and
process point cloud completion by TraPCC to get complete vehicles. Then, we
compare the completed results with the raw object point cloud by MCD and 2D
contour differences from three views. We set a threshold of the score, which
describes the shape differences, to filter the detected objects. The detected
object with the scores above the threshold are determined as a mismatch. In
other words, the shape of the detected object is far from vehicle shapes and
is most likely some noise points, which should be deleted from the detection
results. Experiments show that we can improve the detection precision by
filtering false predictions with TraPCC.

##  5 Experiments

In this section, we introduce the implementation details and evaluate the
performance of TraPCC. Ablation studies are conducted to validate each
component of our approach. We also evaluate the improvement of our TraPCC in
detection tasks.

###  5.1 Dataset

We use two datasets in our experiments, KITTI[15] tracking dataset and
nuScenes[16] dataset, both of which provide the ID information that can be
used to generate the GT-Pool. KITTI tracking dataset has twenty sequences with
different numbers of vehicles, we use one sequence with 5242 vehicles to train
the model and one sequence with 1354 vehicles to test the model. For nuScenes
dataset, we utilze 3262 objects for training and 707 objects for testing.

###  5.2 Implementation Details

3D object detection uses SECOND[32] and PointPillar[33] as backbones on KITTI
tracking dataset and nuScenes. The threshold setting of matching score and
detection score is 0.3 and 0.5 respectively in KITTI and 0.4 and 0.5 in
nuScenes, meaning we only filter the false prediction by matching score when
detection score is below detection threshold.

Evaluation Metric To evaluate the completion results of our model, we design
three kinds of loss. L-G is the CD between the ground truth (partial-GT and
complete-GT) and prediction result on average. L-I is MCD, reflecting the
fidelity of the result and L-S illustrates the shape difference from the side
view, which is computed by the CD of the 2D projected shapes of GT and input.
And meanCD is the average of the above three kinds of Chamfer distances.

Table 1: TraPCC completion results on KITTI nad nuScenes.  Dataset | L-G | L-I | L-S | meanCD
---|---|---|---|---
nuScenes[16] | 0.1232 | 0.1098 | 0.1192 | 0.1175
KITTI[15] | 0.0951 | 0.1031 | 0.0939 | 0.0973

###  5.3 Results

Completion Result on KITTI and nuScene Our method totally use the data from
the raw scan without any template model or complete synthetic ground truth in
the training process, it is unfair to compare our method with paired or
unpaired supervised methods. We only show our results in this section. We
train and test the model on KITTI tracking dataset and nuScenes dataset,
respectively. The result shown in Table.1 illustrate the small shape
difference between the predicted results and GT as well as keeping the
fidelity.

Filter Results for 3D Detection We report the performance on KITTI validation
set in Table. 2. The detection precision can be improved especially for hard
cases, which illustrates TraPCC can definitely help to remove false detected
results. We also use different training datasets to see the generalization
capability of our method. We train the completion network on nuScenes dataset
and use it to boost the detection precision on KITTI dataset. Especially for
the PointPillar-based detection, the cross-dataset training has obvious
improvement.

Table 2: Detection performance on KITTI validation set. K means training on kitti tracking dataset. N means training on nuScenes dataset. We show the results on SECOND and PointPillar two detection backbones. Method |  3D Object Detection$(\%)$ |  BEV Detection$(\%)$
---|---|---
Easy | Moderate | Hard | Easy | Moderate | Hard
SECOND[32] | 81.78 | 71.75 | 65.91 | 87.06 | 83.24 | 83.00
TraPCC(K) | 81.89 | 71.87 | 65.98 | 87.09 | 83.24 | 83.23
TraPCC(N) | 81.84 | 71.86 | 65.92 | 87.06 | 83.17 | 83.26
PointPillar[33] | 85.00 | 75.49 | 69.05 | 88.54 | 85.99 | 84.45
TraPCC(K) | 85.02 | 75.49 | 73.84 | 88.54 | 85.99 | 85.64
TraPCC(N) | 85.00 | 75.49 | 73.85 | 88.54 | 85.95 | 85.66
Table 3: Ablation studies for different modules on KITTI.  Module | C-Net | CP-Net | TraPCC
---|---|---|---
meanCD | 0.0984 | 0.0975 | 0.0973
Fig. 5: Visualization comparison on KITTI.

###  5.4 Ablation Study

In this section, we perform the ablation study to verify the effect of
different components of TraPCC from both quantitative and qualitative aspects
as Table. 3 and Figure. 5 shows. The different networks and analysis are as
follows.

#### C-Net

We use the PCN [17] as the backbone and generate whole complete bodies of
input vehicles directly. We can see from the results that it can still get
reasonable results by training on our GT-pool.

#### P-Net

We stitch the front part prediction and back part prediction together to get
the results of P-Net. From the visualization, it is easy to see that the local
geometries are reconstructed well but the combination result lacks the overall
coordination.

#### CP-Net

We integrate the P-Net and C-Net to a CP-Net. In other words, CP-Net is the
TraPCC without the scene graph (Figure. 2). By considering both the local
detailed geometries and global shape features, CP-Net can reduce the meanCD
and get better results than P-Net and C-Net.

#### TraPCC

After adding scene graph, the network can optimize the result by involving
more occlusion guidance from neighbor’s information. It can be observed that
this module contributes an improvement to the network and reach the best
performance. From the visualization, it not only approach to the ground truth,
but also remove some noise in ground truth.

Fig. 6: Limitation of TraPCC in very sparse point cloud.

###  5.5 Limitations and Future Work

For LiDAR captured point clouds, apart from the severely occluded situations,
the objects far from the LiDAR sensor also have extremely sparse points, which
bring difficulties for the completion because of losing information. TraPCC
can handle many challenging cases as Figure. 5 (last two rows) shows. However
it could not work well all the time(Figure. 6). In the future, we aim to
refine this work from two aspects. One is using some optimization methods to
refine the GT-pool. The other is considering the temporal information in the
input to use more geometry features of the target object with more points from
consecutive views, which gives more guidance for the completion.

##  6 Conclusion

We propose a self-supervised method for point cloud completion on real traffic
scenes without any template or synthetic data. We select the objects in real
scans with enough points and relative complete shapes into our ground truth
pool, so that our prediction results approach the real point clouds captured
by scan sensors, which solves the gap between synthetic and real data existing
in previous methods. We design a bottom-up mechanism to make the network focus
on both local and global features. Scene graph is proposed to utilize scene
information for completion. Experiments demonstrate the effectiveness and
generalization of our method. We also show our method can benefit downstream
3D detection task.

## References

  * [1] Wei Li, CW Pan, Rong Zhang, JP Ren, YX Ma, et al.,  “Aads: Augmented autonomous driving simulation using data-driven algorithms,”  Science robotics, vol. 4, no. 28, 2019.
  * [2] Angela Dai, Angel X. Chang, and etc.,  “Scannet: Richly-annotated 3d reconstructions of indoor scenes,”  CVPR, pp. 2432–2443, 2017.
  * [3] Peishan Cong, Xinge Zhu, and Yuexin Ma,  “Input-output balanced framework for long-tailed lidar semantic segmentation,”  in ICME. IEEE, 2021, pp. 1–6.
  * [4] Xinge Zhu, Hui Zhou, Tai Wang, Fangzhou Hong, Yuexin Ma, Wei Li, Hongsheng Li, and Dahua Lin,  “Cylindrical and asymmetrical 3d convolution networks for lidar segmentation,”  in CVPR, 2021.
  * [5] Yongheng Zhao, Tolga Birdal, Haowen Deng, and Federico Tombari,  “3d point capsule networks,”  in CVPR, 2019, pp. 1009–1018.
  * [6] Xiaogang Wang, Marcelo H Ang Jr, and Gim Hee Lee,  “Cascaded refinement network for point cloud completion,”  in CVPR, 2020, pp. 790–799.
  * [7] Xin W, Tianyang L, Zhizhong H, and Yu-Shen L,  “Point cloud completion by skip-attention network with hierarchical folding,”  in CVPR, 2020, pp. 1939–1948.
  * [8] Wenxiao Zhang, Qingan Yan, and Chunxia Xiao,  “Detail preserved point cloud completion via separated feature aggregation,”  in ECCV. Springer, 2020, pp. 512–528.
  * [9] Haozhe Xie, Hongxun Yao, Shangchen Zhou, Jiageng Mao, Shengping Zhang, and Wenxiu Sun,  “Grnet: Gridding residual network for dense point cloud completion,”  in ECCV. Springer, 2020, pp. 365–381.
  * [10] Angel X. Chang, Thomas A. Funkhouser, Leonidas J. Guibas, Pat Hanrahan, Qixing Huang, et al.,  “Shapenet: An information-rich 3d model repository,”  ArXiv, vol. abs/1512.03012, 2015.
  * [11] Xuelin Chen, Baoquan Chen, and Niloy J Mitra,  “Unpaired point cloud completion on real scans using adversarial training,”  arXiv preprint arXiv:1904.00069, 2019.
  * [12] Rundi Wu, Xuelin Chen, Yixin Zhuang, and Baoquan Chen,  “Multimodal shape completion via conditional generative adversarial networks,”  in ECCV. Springer, 2020, pp. 281–296.
  * [13] Junzhe Zhang, Xinyi Chen, Zhongang Cai, Liang Pan, and etc Zhao,  “Unsupervised 3d shape completion through gan inversion,”  in CVPR, 2021, pp. 1768–1777.
  * [14] Xin Wen, Zhizhong Han, and etc Cao,  “Cycle4completion: Unpaired point cloud completion using cycle transformation with missing region coding,”  in CVPR, 2021, pp. 13080–13089.
  * [15] Andreas Geiger, Philip Lenz, Christoph Stiller, and Raquel Urtasun,  “Vision meets robotics: The kitti dataset,”  IJRR, vol. 32, no. 11, pp. 1231–1237, 2013.
  * [16] Holger C, Varun B, Alex H Lang, Sourabh V, V Erin L, Qiang X, Anush K, Y P, Giancarlo B, and Oscar B,  “nuscenes: A multimodal dataset for autonomous driving,”  CVPR, pp. 11621–11631, 2020.
  * [17] Wentao Y, Tejas K, David H, Christoph M, and Martial H,  “Pcn: Point completion network,”  in 2018 International Conference on 3D Vision (3DV). IEEE, 2018, pp. 728–737.
  * [18] Duc Thanh Nguyen, Binh-Son Hua, Khoi Tran, Quang-Hieu Pham, and Sai-Kit Yeung,  “A field model for repairing 3d shapes,”  in CVPR, 2016, pp. 5676–5684.
  * [19] Wei Z, Shuming G, and Hongwei L,  “A robust hole-filling algorithm for triangular mesh,”  The Visual Computer, vol. 23, no. 12, pp. 987–997, 2007.
  * [20] Matthew Berger, Andrea Tagliasacchi, Lee Seversky, Pierre Alliez, Joshua Levine, Andrei Sharf, and Claudio Silva,  “State of the art in surface reconstruction from point clouds,”  in Eurographics 2014-State of the Art Reports, 2014, vol. 1, pp. 161–185.
  * [21] Minhyuk Sung, Vladimir G Kim, Roland Angst, and Leonidas Guibas,  “Data-driven structural priors for shape completion,”  TOG, vol. 34, no. 6, pp. 1–11, 2015.
  * [22] Liangliang N, Ke X, and Andrei S,  “A search-classify approach for cluttered indoor scene understanding,”  TOG, vol. 31, no. 6, pp. 1–10, 2012.
  * [23] Chao-Hui Shen, Hongbo Fu, Kang Chen, and Shi-Min Hu,  “Structure recovery by part assembly,”  TOG, vol. 31, no. 6, pp. 1–11, 2012.
  * [24] Guo Li, Ligang Liu, Hanlin Zheng, and Niloy J Mitra,  “Analysis, reconstruction and manipulation using arterial snakes,”  TOG, vol. 29, no. 6, pp. 152, 2010.
  * [25] Yan Xu, Xinge Zhu, Jianping Shi, Guofeng Zhang, Hujun Bao, and Hongsheng Li,  “Depth completion from sparse lidar data with depth-normal constraints,”  in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2019, pp. 2811–2820.
  * [26] Zitian Huang, Yikuan Yu, Jiawen Xu, Feng Ni, and Xinyi Le,  “Pf-net: Point fractal network for 3d point cloud completion,”  in CVPR, 2020, pp. 7662–7670.
  * [27] Yinyu Nie, Yiqun Lin, Xiaoguang Han, Shihui Guo, Jian Chang, Shuguang Cui, and Jian Jun Zhang,  “Skeleton-bridged point completion: From global inference to local adjustment,”  NeurIPS, 2020.
  * [28] Muhammad S, Hyunjoo Jenny L, and Young M K,  “Rl-gan-net: A reinforcement learning agent controlled gan network for real-time point cloud shape completion,”  in CVPR, 2019, pp. 5898–5907.
  * [29] Xumin Yu, Yongming R, Ziyi W, Zuyan Liu, Jiwen Lu, and Jie Zhou,  “Pointr: Diverse point cloud completion with geometry-aware transformers,”  in ICCV, 2021, pp. 12498–12507.
  * [30] David Stutz and Andreas G,  “Learning 3d shape completion from laser scan data with weak supervision,”  in CVPR, 2018, pp. 1955–1964.
  * [31] Haoqiang Fan, Hao Su, and Leonidas J Guibas,  “A point set generation network for 3d object reconstruction from a single image,”  in CVPR, 2017.
  * [32] Yan Yan, Yuxing Mao, and Bo Li,  “Second: Sparsely embedded convolutional detection,”  Sensors, vol. 18, no. 10, pp. 3337, 2018.
  * [33] Alex H Lang, Sourabh Vora, and etc Caesar,  “Pointpillars: Fast encoders for object detection from point clouds,”  in CVPR, 2019, pp. 12697–12705.