Towards Open Temporal Graph Neural Networks
Graph neural networks (GNNs) for temporal graphs have recently attracted
increasing attentions, where a common assumption is that the class set for
nodes is closed. However, in real-world scenarios, it often faces the open set
problem with the dynamically increased class set as the time passes by. This
will bring two big challenges to the existing dynamic GNN methods: (i) How to
dynamically propagate appropriate information in an open temporal graph, where
new class nodes are often linked to old class nodes. This case will lead to a
sharp contradiction. This is because typical GNNs are prone to make the
embeddings of connected nodes become similar, while we expect the embeddings of
these two interactive nodes to be distinguishable since they belong to
different classes. (ii) How to avoid catastrophic knowledge forgetting over old
classes when learning new classes occurred in temporal graphs. In this paper,
we propose a general and principled learning approach for open temporal graphs,
called OTGNet, with the goal of addressing the above two challenges. We assume
the knowledge of a node can be disentangled into class-relevant and
class-agnostic one, and thus explore a new message passing mechanism by
extending the information bottleneck principle to only propagate class-agnostic
knowledge between nodes of different classes, avoiding aggregating conflictive
information. Moreover, we devise a strategy to select both important and
diverse triad sub-graph structures for effective class-incremental learning.
Extensive experiments on three real-world datasets of different domains
demonstrate the superiority of our method, compared to the baselines.
Kaituo Feng, Changsheng Li, Xiaolu Zhang, Jun Zhou
# Towards Open Temporal Graph Neural Networks

###### Abstract

Graph neural networks (GNNs) for temporal graphs have recently attracted increasing attentions, where a common assumption is that the class set for nodes is closed. However, in real-world scenarios, it often faces the open set problem with the dynamically increased class set as the time passes by. This will bring two big challenges to the existing temporal GNN methods: (i) How to dynamically propagate appropriate information in an open temporal graph, where new class nodes are often linked to old class nodes. This case will lead to a sharp contradiction. This is because typical GNNs are prone to make the embeddings of connected nodes become similar, while we expect the embeddings of these two interactive nodes to be distinguishable since they belong to different classes. (ii) How to avoid catastrophic knowledge forgetting over old classes when learning new classes occurred in temporal graphs. In this paper, we propose a general and principled learning approach for open temporal graphs, called OTGNet, with the goal of addressing the above two challenges. We assume the knowledge of a node can be disentangled into class-relevant and class-agnostic one, and thus explore a new message passing mechanism by extending the information bottleneck principle to only propagate class-agnostic knowledge between nodes of different classes, avoiding aggregating conflictive information. Moreover, we devise a strategy to select both important and diverse triad sub-graph structures for effective class-incremental learning. Extensive experiments on three real-world datasets of different domains demonstrate the superiority of our method, compared to the baselines.

## 1 Introduction

Temporal graph (Nguyen et al., 2018) represents a sequence of time-stamped events (e.g. addition or deletion for edges or nodes) (Rossi et al., 2020), which is a popular kind of graph structure in variety of domains such as social networks (Kleinberg, 2007), citations networks (Feng et al., 2022), topic communities (Hamilton et al., 2017), etc. For instance, in topic communities, all posts can be modelled as a graph, where each node represents one post. New posts can be continually added into the community, thus the graph is dynamically evolving. In order to handle this kind of graph structure, many methods have been proposed in the past decade (Wang et al., 2020; Xu et al., 2020; Rossi et al., 2020; Nguyen et al., 2018; Li et al., 2022). The key to success for these methods is to learn an effective node embedding by capturing temporal patterns based on time-stamped events.

A basic assumption among the above methods is that the class set of nodes is always closed, i.e., the class set is fixed as time passes by. However, in many real-world applications, the class set is open. We still take topic communities as an example, all the topics can be regarded as the class set of nodes for a post-to-post graph. When a new topic is created in the community, it means a new class is involved into the graph. This will bring two challenges to previous approaches: The first problem is the heterophily propagation issue. In an open temporal graph, a node belonging to a new class is often
linked to a node of old class, as shown in Figure 1. In Figure 1, 'class 2' is a new class, and 'class 1' is an old class. There is a link occured at timestamp \(t_{4}\) connecting two nodes \(v_{4}\) and \(v_{5}\), where \(v_{4}\) and \(v_{5}\) belong to different classes. Such a connection will lead to a sharp contradiction. This is because typical GNNs are prone to learn similar embeddings for \(v_{4}\) and \(v_{5}\) due to their connection (Xie et al., 2020; Zhu et al., 2020), while we expect the embeddings of \(v_{4}\) and \(v_{5}\) to be distinguishable since they belong to different classes. We call this dilemma as heterophily propagation. Someone might argue that we can simply drop those links connecting different class nodes. However, this might break the graph structure and lose information. Thus, how and what to transfer between connected nodes of different classes remains a challenge for open temporal graph.

The second problem is the catastrophic forgetting issue. When learning a new class in an open temporal graph, the knowledge of the old class might be catastrophically forgot, thus degrading the overall performance of the model. In the field of computer vision, many incremental learning methods have been proposed (Wu et al., 2019; Tao et al., 2020), which focus on convolutional neural networks (CNNs) for non-graph data like images. If simply applying these methods to graph-structured data by individually treating each node, the topological structure and the interaction between nodes will be ignored. Recently, Wang et al. (2020); Zhou & Cao (2021) propose to overcome catastrophic forgetting for graph data. However, They focus on static graph snapshots, and utilize static GNN for each snapshot, thus largely ignoring fine-grained temporal topological information.

In this paper, we put forward the first class-incremental learning approach towards open temporal dynamic graphs, called OTGNet. To mitigate the issue of heterophily propagation, we assume the information of a node can be disentangled into class-relevant and class-agnostic one. Based on this assumption, we design a new message passing mechanism by resorting to information bottleneck (Alemi et al., 2016) to only propagate class-agnostic knowledge between nodes of different classes. In this way, we can well avoid transferring conflictive information. To prevent catastrophic knowledge forgetting over old classes, we propose to select representative sub-graph structures generated from old classes, and incorporate them into the learning process of new classes. Previous works (Zhou et al., 2018; Zigmani et al., 2014; Huang et al., 2014) point out triad structure (triangle-shape structure) is a fundamental element of temporal graph and can capture evolution patterns. Motivated by this, we devise a value function to select not only important but also diverse triad structures, and replay them for continual learning. Due to the combinational property, optimizing the value function is NP-hard. Thus, we develop a simple yet effective algorithm to find its approximate solution, and give a theoretical guarantee to the lower bound of the approximation ratio. It is worth noting that our message passing mechanism and triad structure selection can benefit from each other. On the one hand, learning good node embeddings by our message passing mechanism is helpful to select more representative triad structure. On the other hand, selecting representative triads can well preserve the knowledge of old classes and thus is good for propagating information more precisely.

Our contributions can be summarized as : 1) Our approach constitutes the first attempt to investigate open temporal graph neural network; 2) We propose a general framework, OTGNet, which can address the issues of both heterophily propagation and catastrophic forgetting; 3) We perform extensive experiments and analyze the results, proving the effectiveness of our method.

## 2 Related Work

Dynamic GNNs can be generally divided into two groups (Rossi et al., 2020) according to the characteristic of dynamic graph: discrete-time dynamic GNNs (Zhou et al., 2018; Goyal et al., 2018; Wang et al., 2020) and continuous-time dynamic GNNs (a.k.a. temporal GNNs (Nguyen et al., 2018)) (Rossi et al., 2020; Trivedi et al., 2019). Discrete-time approaches focus on discrete-time dynamic graph that is a collection of static graph snapshots taken at intervals in time, and contains

Figure 1: An illustration for an open temporal graph. In the beginning, there is an old class (class 1). As the time passes by, a new class (class 2) occurs. \(t_{4}\) denotes the timestamp the edge is built. The edge occurred at \(t_{4}\) connects \(v_{4}\) and \(v_{5}\) (e.g., the same user comments on both post \(v_{4}\) and post \(v_{5}\) in topic communities).
dynamic information at a very coarse level. Continuous-time approaches study continuous-time dynamic graph that represents a sequence of time-stamped events, and possesses temporal dynamics at finer time granularity. In this paper, we focus on temporal GNNs. We first briefly review related works on temporal GNNs, followed by class-incremental learning.

**Temporal GNNs.** In recent years, many temporal GNNs (Kumar et al., 2019; Wang et al., 2021a; Trivedi et al., 2019) have been proposed. For instance, DyRep (Trivedi et al., 2019) took the advantage of temporal point process to capture fine-grained temporal dynamics. CAW (Wang et al., 2021b) retrieved temporal network motifs to represent the temporal dynamics. TGAT (Xu et al., 2020) proposed a temporal graph attention layer to learn temporal interactions. Moreover, TGN (Rossi et al., 2020) proposed an efficient model that can memorize long term dependencies in the temporal graph. However, all of them concentrate on closed temporal graphs, i.e., the class set is always kept unchanged, neglecting that new classes can be dynamically increased in many real-world applications.

**Class-incremental learning.** Class-incremental learning have been widely studied in the computer vision community (Li and Hoiem, 2017; Wu et al., 2019). For example, EWC (Kirkpatrick et al., 2017) proposed to penalize the update of parameters that are significant to previous tasks. iCaRL (Li and Hoiem, 2017) maintained a memory buffer to store representative samples for memorizing the knowledge of old classes and replaying them when learning new classes. These methods focus on CNNs for non-graph data like images. It is obviously not suitable to directly apply them to graph data. Recently, a few incremental learning works have been proposed for graph data (Wang et al., 2020; Zhou and Cao, 2021). ContinualGNN (Wang et al., 2020) proposed a method for closed discrete-time dynamic graph, and trained the model based on static snapshots. ER-GAT (Zhou and Cao, 2021) selected representative nodes for old classes and replay them when learning new tasks. Different from them studying discrete-time dynamic graph, we aim to investigate open temporal graph.

## 3 Proposed Method

### Preliminaries

**Notations.** Let \(\mathcal{G}(t)=\{\mathcal{V}(t),\mathcal{E}(t)\}\) denote a temporal graph at time-stamp \(t\), where \(\mathcal{V}(t)\) is the set of existing nodes at \(t\), and \(\mathcal{E}(t)\) is the set of existing temporal edges at \(t\). Each element \(e_{ij}(t_{k})\in\mathcal{E}(t)\) represents node \(i\) and node \(j\) are linked at time-stamp \(t_{k}(t_{k}\leq t)\). Let \(\mathcal{N}_{i}(t)\) be the neighbor set of node \(i\) at \(t\). We assume \(x_{i}(t)\) denotes the embedding of node \(i\) at \(t\), where \(x_{i}(0)\) is the initial feature of node \(i\). Let \(\mathcal{Y}(t)=\{1,2,\cdots,m(t)\}\) be the class set of all nodes at \(t\), where \(m(t)\) denotes the number of existing classes until time \(t\).

**Problem formulation.** In our open temporal graph setting, as new nodes are continually added into the graph, new classes can occur, i.e., the number \(m(t)\) of classes is increased and thus the class set \(\mathcal{Y}(t)\) is open, rather than a closed one like traditional temporal graph. Thus, we formulate our problem as a sequence of class-incremental tasks \(\mathcal{T}=\{\mathcal{T}_{1},\mathcal{T}_{2},\cdots,\mathcal{T}_{L},\cdots\}\) in chronological order. Each task \(\mathcal{T}_{i}\) contains one or multiple new classes which are never seen in previous tasks \(\{\mathcal{T}_{1},\mathcal{T}_{2},\cdots,\mathcal{T}_{i-1}\}\). In our new problem setting, the goal is to learn an open temporal graph neural network based on current task \(\mathcal{T}_{i}\), expecting our model to not only perform well on current task but also prevent catastrophic forgetting over previous tasks.

### Framework

As aforementioned, there are two key challenges in open temporal graph learning: heterophily propagation and catastrophic forgetting. To address the two challenges, we propose a general framework, OTGNet, as illustrated in Figure 2. Our framework mainly includes two modules : A knowledge preservation module is devised to overcome catastrophic forgetting, which consists of two components: a triad structure selection component is devised to select representative triad structures; a triad structure replay component is designed for replaying the selected triads to avoid catastrophic forgetting. An information bottleneck based message passing module is proposed to propagate class-agnostic knowledge between different class nodes, which can address the heterophily propagation issue. Next, we will elaborate each module of our framework.

Figure 2: An illustration of overall architecture.
### Knowledge Preservation over Old Class

When learning new classes based on current task \(\mathcal{T}_{i}\), it is likely for the model to catastrophically forget knowledge over old classes from previous tasks. If we combine all data of old classes with the data of new classes for retraining, the computational complexities will be sharply increased, and be not affordable. Thus, we propose to select representative structures from old classes to preserve knowledge, and incorporate them into the learning process of new classes for replay.

**Triad Structure Selection.** As previous works (Zhou et al., 2018; Zignani et al., 2014; Huang et al., 2014) point out, the triad structure is a fundamental element of temporal graph and its triad closure process could demonstrate the evolution patterns. According to Zhou et al. (2018), the triads have two types of structures: closed triad and open triad, as shown in Figure 3. A closed triad consists of three vertices connected with each other, while an open triad has two of three vertices not connected with each other. The closed triad can be developed from an open triad, and the triad closure process is able to model the evolution patterns (Zhou et al., 2018). Motivated by this point, we propose a new strategy to preserve the knowledge of old classes by selecting representative triad structures from old classes. However, how to measure the'representativeness' of each triad, and how to select some triads to represent the knowledge of old classes have been not explored so far.

To write conveniently, we omit \(t\) for all symbols in this section. Without loss of generality, we denote a closed triad for class \(k\) as \(g^{c}_{k}=(v_{s},v_{p},v_{q})\), where all of three nodes \(v_{s},v_{p},v_{q}\) belong to class \(k\) and \(v_{s},v_{p},v_{q}\) are pairwise connected, i.e., \(e_{sp}(t_{i}),e_{sq}(t_{j}),e_{pq}(t_{l})\in\mathcal{E}(t_{m})\) and \(t_{i},t_{j}<t_{l},t_{m}\) is the last time-stamp of the graph. We denote an open triad for class \(k\) as \(g^{o}_{k}=(v_{s},v_{p},v_{q})\) with \(v_{p}\) and \(v_{q}\) not linked to each other in the last observation of the graph, i.e., \(e_{\bar{s}p}(t_{i}),e_{\bar{s}q}(t_{j})\in\mathcal{E}(t_{m})\) and \(e_{\bar{p}\bar{q}}\notin\mathcal{E}(t_{m})\). Assuming \(S^{c}_{k}=\{g^{c}_{k,1},g^{c}_{k,2},...,g^{c}_{k,M}\}\) and \(S^{o}_{k}=\{g^{o}_{k,1},g^{o}_{k,2},...,g^{o}_{k,M}\}\) is the selected closed triad set and open triad set for class \(k\), respectively. \(M\) is the memory budget for each class. Next, we introduce how to measure and select closed triads \(S^{c}_{k}\). It is analogous to open triads \(S^{o}_{k}\).

In order to measure the'representativeness' of each triad, one intuitive and reasonable thought is to see how the performance of the model is affected if removing this triad from the graph. However, if we retrain the model once one triad is removed, the time cost is prohibitive. Inspired by the influence function aiming to estimate the parameter changes of the machine learning model when removing a training sample (Koh and Liang, 2017), we extend the influence function to directly estimate the'representativeness' of each triad structure without retraining, and propose an objective function as:

\[\mathcal{I}_{loss}(g^{c}_{k},\theta) =\left.\frac{\mathrm{d}\,\mathcal{L}(G_{k},\theta,g^{c}_{k})}{ \mathrm{d}\,\varepsilon}\right|_{\varepsilon=0}=\nabla_{\theta}\mathcal{L}(G_{ k},\theta)^{\top}\frac{\mathrm{d}\,\hat{\theta}_{e,g^{c}_{k}}}{\mathrm{d}\, \varepsilon}\right|_{\varepsilon=0} \tag{1}\] \[=-\nabla_{\theta}\mathcal{L}(G_{k},\theta)^{\top}\hat{H}^{-1}_{ \theta}\nabla_{\theta}\mathcal{L}(g^{c}_{k},\theta)\]

where \(\mathcal{L}\) represents the loss function, e.g., cross-entropy used in this paper. \(\theta\) is the parameter of the model, and \(G_{k}\) is the node set of class \(k\). \(\theta_{e,g^{c}_{k}}\) is the retrained parameter if we upweight three nodes in \(g^{c}_{k}\) by \(\varepsilon(\varepsilon\to 0)\) during training. \(\varepsilon\) is a small weight added on the three nodes of the triad \(g^{c}_{k}\) in the loss function \(\mathcal{L}\). \(H_{\theta}\) is the Hessian matrix. \(\nabla_{\theta}\mathcal{L}(g^{c}_{k},\theta)\), \(\nabla_{\theta}\mathcal{L}(G_{k},\theta)\) are the gradients of the loss to \(g^{c}_{k}\) and \(G_{k}\), respectively. The full derivation of Eq. (1) is in Appendix A.2.

In Eq. (1), \(\mathcal{I}_{loss}(g^{c}_{k},\theta)\) estimates the influence of the triad \(g^{c}_{k}\) on the model performance for class \(k\). The more negative \(\mathcal{I}_{loss}(g^{c}_{k},\theta)\) is, the more positive influence on model performance \(g^{c}_{k}\) provides, in other words, the more important \(g^{c}_{k}\) is. Thus, we define the'representativeness' of a triad structure as:

\[\mathcal{R}(g^{c}_{k})=-\mathcal{I}_{loss}(g^{c}_{k},\theta) \tag{2}\]

In order to well preserve the knowledge of old classes, we expect all \(g^{c}_{k}\) in \(S^{c}_{k}\) are important, and propose the following objective function to find \(S^{c}_{k}\):

\[S^{c}_{k}=\arg\max_{\{g^{c}_{k,1},\cdots,g^{c}_{k,M}\}}\sum_{i=1}^{M}\mathcal{ R}(g^{c}_{k,i}) \tag{3}\]

During optimizing (3), we only take the triad \(g^{c}_{k,i}\) with positive \(\mathcal{R}(g^{c}_{k,i})\) as the candidate, since \(g^{c}_{k,i}\) with negative \(\mathcal{R}(g^{c}_{k,i})\) can be thought to be harmful to the model performance. We note that only

Figure 3: An illustration for closed triad and open triad.
optimizing (3) might lead to that the selected \(g^{c}_{k,i}\) have similar functions. Considering this, we hope \(S^{c}_{k}\) should be not only important but also diverse. To do this, we first define:

\[\mathcal{C}(g^{c}_{k,i})=\{g^{c}_{k,j}|\left|\left|\bar{x}(g^{c}_{k,j})-\bar{x} (g^{c}_{k,i})\right|\right|_{2}\leq\delta,g^{c}_{k,j}\in N^{c}_{k}\}, \tag{4}\]

where \(\bar{x}(g^{c}_{k,j})\) denotes the average embedding of three vertices in \(g^{c}_{k,j}\). \(N^{c}_{k}\) denotes the set containing all positive closed triads for class \(k\), and \(\delta\) is a similar radius. \(\mathcal{C}(g^{c}_{k,i})\) measures the number of \(g^{c}_{k,j}\), where the distance of \(\bar{x}(g^{c}_{k,j})\) and \(\bar{x}(g^{c}_{k,i})\) is less or equal to \(\delta\). To make the selected triads \(S^{c}_{k}\) diverse, we also anticipate that \(\{\mathcal{C}(g^{c}_{k,1}),\cdots,\mathcal{C}(g^{c}_{k,M})\}\) can cover different triads as many as possible by:

\[S^{c}_{k}=\arg\max_{\{g^{c}_{k,1},\cdots,g^{c}_{k,M}\}}\frac{|\bigcup_{i=1}^{M }\mathcal{C}(g^{c}_{k,i})|}{|N^{c}_{k}|} \tag{5}\]

Finally, we combine (5) with (3), and present the final objective function for triad selection as:

\[S^{c}_{k}=\arg\max_{\{g^{c}_{k,1},\cdots,g^{c}_{k,M}\}}F(S^{c}_{k})=\arg\max_{ \{g^{c}_{k,1},\cdots,g^{c}_{k,M}\}}\left(\sum_{i=1}^{M}\mathcal{R}(g^{c}_{k,i} )+\gamma\frac{|\bigcup_{i=1}^{M}\mathcal{C}(g^{c}_{k,i})|}{|N^{c}_{k}|}\right) \tag{6}\]

where \(\gamma\) is a hyper-parameter. By (6), we can select not only important but also diverse triads to preserve the knowledge of old classes.

Due to the combinatorial property, solving (6) is NP-hard. Fortunately, we show that \(F(S^{c}_{k})\) satisfies the condition of monotone and submodular. The proof can be found in Appendix A.3. Based on this property, (6) could be solved by a greedy algorithm (Pokutta et al., 2020) with an approximation ratio guarantee, by the following Theorem 1(Krause and Golovin, 2014).

**Theorem 1**.: Assuming our value function \(F:2^{N}\rightarrow\mathbb{R}_{+}\) is monotone and submodular. If \(S^{c}_{k}\) is an optimal triad set and \(S^{c}_{k}\) is a triad set selected by the greedy algorithm (Pokutta et al., 2020), then \(F(S^{c}_{k})\geq(1-\frac{1}{\epsilon})F(S^{c}_{k})\) holds.

By Theorem 1, we can greedily select closed triads as in Algorithm 1. As aforementioned, the open triad set \(S^{o}_{k}\) can be chosen by the same method. The proof of Theorem 1 can be found in Krause and Golovin (2014).

An Acceleration Solution.We first provide the time complexity analysis of triad selection. When counting triads for class \(k\), we first enumerate the edge that connects two nodes \(v_{s}\) and \(v_{d}\) of class \(c\). Then, for each neighbor node of \(v_{s}\) that belongs to class \(k\), we check whether this neighbor node links to \(v_{d}\). If this is the case and the condition of temporal order is satisfied, these three nodes form a closed triad, otherwise these three nodes form an open triad. Thus, a rough upper bound of the number of closed triads in class \(k\) is \(O(d_{k}|\mathcal{E}_{k}|)\), where \(|\mathcal{E}_{k}|\) is the number of edges between two nodes of class \(k\), and \(d_{k}\) is the max degree of nodes of class \(k\). When selecting closed triads, finding a closed triad that maximizes the value function takes \(O(|N^{c}_{k}|^{2})\), where \(|N^{c}_{k}|\) is the number of positive closed triads in class \(k\). Thus, it is of order \(O(M|N^{c}_{k}|^{2})\) for selecting the closed triad set \(S^{c}_{k}\), where \(M\) is the memory budget for each class. The time complexity for selecting the open triads is the same.

To accelerate the selection process, a natural idea is to reduce \(N^{c}_{k}\) by only selecting closed triads from \(g^{c}_{k}\) with large values of \(\mathcal{R}(g^{c}_{k})\). Specifically, we sort the closed triad \(g^{c}_{k}\) based on \(\mathcal{R}(g^{c}_{k})\), and use the top-\(K\) ones as the candidate set \(N^{c}_{k}\) for selection. The way for selecting open triads is the same.

```
1:all triads \(N^{c}_{k}\) for class \(k\), budget \(M\);
2:representative triad set \(S^{c}_{k}\);
3:Initialize \(S^{c}_{k}=\emptyset\);
4:while\(|S^{c}_{k}|<M\)do
5:\(u=argmax_{u\in N^{c}_{k}\setminus S^{c}_{k}}F(S^{c}_{k}\cup\{u\})\);
6:\(S^{c}_{k}=S^{c}_{k}\cup u\);
7:endwhile
8:return\(S^{c}_{k}\)
```

**Algorithm 1** Representative triad selection

**Triad Structure Replay.** After obtaining representative closed and open triad sets, \(S^{c}_{k}\) and \(S^{o}_{k}\), we will replay these triads from old classes when learning new classes, so as to overcome catastrophic forgetting. First, we hope the model is able to correctly predict the labels of nodes from the selected triad set, and thus use the cross entropy loss \(\mathcal{L}_{ce}\) for each node in the selected triad set.

Moreover, as mentioned above, the triad closure process can capture the evolution pattern of a dynamic graph. Thus, we use the link prediction loss \(\mathcal{L}_{link}\) to correctly predict the probability whether two nodes are connected based on the closed and open triads, to further preserve knowledge:

\[\mathcal{L}_{link}=-\frac{1}{N_{c}}\sum_{i=1}^{N_{c}}\log(\sigma(x^{i}_{p}{(t) }^{\top}x^{i}_{q}(t)))-\frac{1}{N_{o}}\sum_{i=1}^{N_{o}}\log(1-\sigma(\tilde{x} ^{i}_{p}{(t)}^{\top}\bar{x}^{i}_{q}(t))), \tag{7}\]
where \(N_{c}\),\(N_{o}\) are the number of closed, open triads respectively, where \(N_{c}=N_{o}=N_{t}*M\). \(N_{t}\) is the number of old classes. \(\sigma\) is the sigmoid function. \(x_{p}^{i}(t),x_{q}^{i}(t)\) are the embeddings of \(v_{p}\), \(v_{q}\) of the \(i^{th}\) closed triad. \(\tilde{x}_{p}^{i}(t)\), \(\tilde{x}_{q}^{i}(t)\) are the embeddings of \(v_{\tilde{p}}\), \(v_{\tilde{q}}\) of the \(i^{th}\) open triad. Here the closed triads and open triads serve as postive samples and negative samples, respectively.

### Message Passing via Information Bottleneck

When new class occurs, it is possible that one edge connects one node of the new class and one node of an old class, as shown in Figure 1. To avoid aggregating conflictive knowledge between nodes of different classes, one intuitive thought is to extract class-agnostic knowledge from each node, and transfer the class-agnostic knowledge between nodes of different classes To do this, we extend the information bottleneck principle to obtain a class-agnostic representation for each node.

**Class-agnostic Representation.** Traditional information bottleneck aims to learn a representation that preserves the maximum information about the class while has minimal mutual information with the input (Tishby et al., 2000). Differently, we attempt to extract class-agnostic representations from an opposite view, i.e., we expect the learned representation has minimum information about the class, but preserve the maximum information about the input. Thus, we propose an objective function as:

\[J_{IB}=\min_{Z(t)}\;I(Z(t),Y)-\beta I(Z(t),X(t)), \tag{8}\]

where \(\beta\) is the Lagrange multiplier. \(I(\cdot,\cdot)\) denotes the mutual information. \(X(t)\), \(Z(t)\) are the random variables of the node embeddings and class-agnostic representations at time-stamp \(t\). \(Y\) is the random variable of node label. In this paper, we adopt a two-layer MLP for mapping \(X(t)\) to \(Z(t)\).

However, directly optimizing (8) is intractable. Thus, we utilize CLUB (Cheng et al., 2020) to estimate the upper bound of \(I(Z(t),Y)\) and utilize MINE (Belghazi et al., 2018) to estimate the lower bound of \(I(Z(t),X(t))\). Thus, the upper bound of our objective could be written as:

\[J_{IB}\leq\mathcal{L}_{IB}=\mathbb{E}_{p(Z(t),Y)}[\log q_{\mu}(y |z(t))]-\mathbb{E}_{p(Z(t))}\mathbb{E}_{p(Y)}[\log q_{\mu}(y|z(t))]\\ -\beta(\sup_{\psi}\mathbb{E}_{p(X(t),Z(t))}[T_{\psi}(x,z(t))]- \log(\mathbb{E}_{p(X(t))p(Z(t))}[e^{T_{\psi}(x(t),z(t))}])). \tag{9}\]

where \(z(t)\), \(x(t)\), \(y\) are the instances of \(Z(t)\), \(X(t)\), \(Y\) respectively. \(T_{\psi}:\mathcal{X}\times\mathcal{Z}\rightarrow\mathbb{R}\) is a neural network parametrized by \(\psi\). Since \(p(y|z(t))\) is unknown, we introduce a variational approximation \(q_{\mu}(y|z(t))\) to approximate \(p(y|z(t))\) with parameter \(\mu\). By minimizing this upper bound \(\mathcal{L}_{IB}\), we can obtain an approximation solution to Eq. (8). The derivation of formula (9) is in Appendix A.1.

It is worth noting that \(z_{i}(t)\) is an intermediate variable as the class-agnostic representation of node \(i\). We only use \(z_{i}(t)\) to propagate information to other nodes having different classes from node \(i\). If one node \(j\) has the same class with node \(i\), we still use \(x_{i}(t)\) for information aggregation of node \(j\), so as to avoid losing information. In this way, the heterophily propagation issue can be well addressed.

**Message Propagation.** In order to aggregate temporal information and topological information in temporal graph, many information propagation mechanism have been proposed (Rossi et al., 2020; Xu et al., 2020). Here, we extend a typical mechanism proposed in TGAT (Xu et al., 2020), and present the following way to learn the temporal attention coefficient as:

\[a_{ij}(t)=\frac{\exp(([x_{i}(t)||\Phi(t-t_{i})]W_{q})^{\top}([h_{j}(t)||\Phi (t-t_{j})|W_{p}))}{\sum_{l\in\mathcal{N}_{l}(t)}\exp(([x_{i}(t)||\Phi(t-t_{i} )]W_{q})^{\top}([h_{l}(t)||\Phi(t-t_{l})]W_{p}))} \tag{10}\]

where \(\Phi\) is a time encoding function proposed in TGAT. \(||\) represents the concatenation operator. \(W_{p}\) and \(W_{q}\) are two learnt parameter matrices. \(t_{i}\) is the time of the last interaction of node \(i\). \(t_{j}\) is the time of the last interaction between node \(i\) and node \(j\). \(t_{l}\) is the time of the last interaction between node \(i\) and node \(l\). Note that we adopt different \(h_{l}(t)\) from that in the original TGAT, defined as:

\[h_{l}(t)=\begin{cases}x_{l}(t),&y_{i}=y_{l}\\ z_{l}(t),&y_{i}\neq y_{l}\end{cases}, \tag{11}\]

where \(h_{l}(t)\) is the message produced by neighbor node \(l\in\mathcal{N}_{i}(t)\). If node \(l\) and \(i\) have different classes, we leverage its class-agnostic representation \(z_{l}(t)\) for information aggregation of node \(i\), otherwise we directly use its embedding \(x_{l}(t)\) for aggregating. Note that our method supports multiple layers of network. We do not use the symbol of the layer only for writing conveniently.
Finally, we update the embedding of node \(i\) by aggregating the information from its neighbors:

\[x_{i}(t)=\sum_{j\in\mathcal{N}_{i}(t)}a_{ij}(t)W_{h}h_{j}(t), \tag{12}\]

where \(W_{h}\) is a learnt parameter matrix for message aggregation.

### Optimization

During training, we first optimize the information bottleneck loss \(\mathcal{L}_{IB}\). Then, we minimize \(\mathcal{L}=\mathcal{L}_{ce}+\rho\mathcal{L}_{link}\), where \(\rho\) is the hyper-parameter and \(\mathcal{L}_{ce}\) is the node classification loss over both nodes of new classes and that of the selected triads. We alternatively optimize them until convergence. The detailed training procedure and pseudo-code could be found in Appendix A.5.

In testing, we extract an corresponding embedding of a test node by assuming its label to be the one that appears the most times among its neighbor nodes in the training set, due to referring to extracting class-agnostic representations. After that, we predict the label of test nodes based on the extracted embeddings.

## 4 Experiments

### Experiment Setup

**Datasets.** We construct three real-world datasets to evaluate our method: Reddit (Hamilton et al., 2017), Yelp (Sankar et al., 2020), Taobao (Du et al., 2019). In Reddit, we construct a post-to-post graph. Specifically, we treat posts as nodes and treat the subreddit (topic community) a post belongs to as the node label. When a user comments two posts with the time interval less or equal to a week, a temporal edge between the two nodes will be built. We regard the data in each month as a task, where July to December in 2009 are used. In each month, we sample \(3\) large communities that do not appear in previous months as the new classes. For Yelp dataset, we construct a business-to-business temporal graph from 2015 to 2019 in the same way as Reddit. For Taobao dataset, we construct an item-to-item graph in the same way as Reddit in a 6-days promotion season of Taobao. Table 1 summarizes the statistics of these datasets. More information about datasets could be found in Appendix A.4.

**Experiment Settings.** For each task, we use \(80\%\) nodes for training, \(10\%\) nodes for validation, \(10\%\) nodes for testing. We use two widely-used metrics in class-incremental learning to evaluate our method (Chaudhry et al., 2018; Bang et al., 2021): AP and AF. Average Performance (AP) measures the average performance of a model on all previous tasks. Here we use accuracy to measure model performance. Average Forgetting (AF) measures the decreasing extent of model performance on previous tasks compared to the best ones. More implementation details is in Appendix A.6.

**Baselines.** First, we compare with three incremental learning methods based on static GNNs: ERGAT (Zhou and Cao, 2021), TWC-GAT (Liu et al., 2021) and ContinualGNN (Wang et al., 2020). For ER-GAT and TWC-GAT, we use the final state of temporal graph as input in each task. Since ContinualGNN is based on snapshots, we split each task into \(10\) snapshots. In addition, we combine three representative temporal GNN (TGAT (Xu et al., 2020), TGN (Rossi et al., 2020), TREND (Wen and Fang, 2022)) and three widely-used class-incremental learning methods in computer vision (EWC (Kirkpatrick et al., 2017), iCaRL (Rebuffi et al., 2017), BiC (Wu et al., 2019)) as baselines. For our method, we set \(M\) as \(10\) on all the datasets.

### Results and Analysis

**Overall Comparison.** As shown in Table 2, our method outperform other methods by a large margin. The reasons are as follows. For the first three methods, they are all based on static GNN that can not capture the fine-grained dynamics in temporal graph. TGN, TGAT and TREND are three dynamic GNNs with fixed class set. When applying three typical class-incremental learning methods to TGN,

\begin{table}
\begin{tabular}{c c c c} \hline \hline  & Reddit & Yelp & Taobao \\ \hline \# Nodes & 10845 & 15617 & 114232 \\ \# Edges & 216397 & 56985 & 455662 \\ \# Total classes & 18 & 15 & 90 \\ \# Timespan & 6 months & 5 years & 6 days \\ \hline \# Tasks & 6 & 5 & 3 \\ \# Classes per task & 3 & 3 & 30 \\ \# Timespan per task & 1 month & 1 year & 2 days \\ \hline \hline \end{tabular}
\end{table}
Table 1: Dataset Statistics
TGAT and TREND, the phenomenon of catastrophic forgetting is alleviating. However, they still suffer from the issue of heterophily propagation.

**Performance Analysis of Different Task Numbers.** To provide further analysis of our method, we plot the performance changes of different methods along with the increased tasks. As shown in Figure 4, our method generally achieves better performance than baselines as the task number increases. Since Bic based methods achieve better performance based on Table 2, we do not report the results of the other two incremental learning based methods. In addition, the curves of OTGNet are smoother that those of other methods, which indicates our method can well address the issue of catastrophic forgetting. Because of space limitation, we provide the curves of AF in Appendix A.7.

**Ablation Study of our proposed propagation mechanism.** We further study the effectiveness of our information bottleneck based message propagation mechanism. OTGNet-w.o.-IB represents our method directly transferring the embeddings of neighbor nodes instead of class-agnostic representations. OTGNet-w.o.-prop denotes our method directly dropping the links between nodes of different classes. We take GBK-GNN (Du et al., 2022) as another baseline, where GBK-GNN originally handles the heterophily for static graph. For a fair comparison, we modify GBK-GNN to an open temporal graph: Specifically, we create two temporal message propagation modules with separated parameters as the two kernel feature transformation matrices in GBK-GNN. We denote

\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{Method} & \multicolumn{2}{c}{Reddit} & \multicolumn{2}{c}{Yelp} & \multicolumn{2}{c}{TaoBao} \\ \cline{2-7}  & AP(\(\uparrow\)) & AF(\(\downarrow\)) & AP(\(\uparrow\)) & AF(\(\downarrow\)) & AP(\(\uparrow\)) & AF(\(\downarrow\)) \\ \hline ContinualGNN & 52.17 \(\pm\) 2.46 & 25.59 \(\pm\) 5.39 & 49.73 \(\pm\) 0.27 & 28.76 \(\pm\) 1.52 & 58.39 \(\pm\) 0.24 & 47.03 \(\pm\) 0.50 \\ ER-GAT & 52.03 \(\pm\) 2.59 & 22.67 \(\pm\) 3.30 & 62.05 \(\pm\) 0.70 & 18.91 \(\pm\) 1.09 & 70.09 \(\pm\) 0.88 & 23.24 \(\pm\) 0.36 \\ TWC-GAT & 52.88 \(\pm\) 0.53 & 19.60 \(\pm\) 3.64 & 60.90 \(\pm\) 3.74 & 16.92 \(\pm\) 0.63 & 59.91 \(\pm\) 1.71 & 42.78 \(\pm\) 1.39 \\ \hline TGAT & 48.47 \(\pm\) 1.81 & 31.03 \(\pm\) 4.48 & 64.89 \(\pm\) 1.27 & 27.31 \(\pm\) 3.99 & 60.62 \(\pm\) 0.23 & 43.35 \(\pm\) 0.77 \\ TGAT+EWC & 50.16 \(\pm\) 2.45 & 28.27 \(\pm\) 4.00 & 66.58 \(\pm\) 3.11 & 25.48 \(\pm\) 1.75 & 64.03 \(\pm\) 0.62 & 38.26 \(\pm\) 1.20 \\ TGAT+CaRL & 54.50 \(\pm\) 2.04 & 27.66 \(\pm\) 1.11 & 71.71 \(\pm\) 2.48 & 17.56 \(\pm\) 2.46 & 73.74 \(\pm\) 1.40 & 23.90 \(\pm\) 2.04 \\ TGAT+BiC & 54.61 \(\pm\) 0.89 & 25.42 \(\pm\) 2.72 & 74.73 \(\pm\) 3.54 & 16.42 \(\pm\) 4.41 & 74.05 \(\pm\) 0.48 & 23.27 \(\pm\) 0.65 \\ \hline TGN & 47.49 \(\pm\) 0.48 & 32.06 \(\pm\) 1.91 & 56.24 \(\pm\) 1.65 & 41.27 \(\pm\) 2.30 & 65.89 \(\pm\) 1.20 & 36.15 \(\pm\) 1.55 \\ TGN+EWC & 49.45 \(\pm\) 1.45 & 31.74 \(\pm\) 1.11 & 60.83 \(\pm\) 3.55 & 35.73 \(\pm\) 3.48 & 68.89 \(\pm\) 2.09 & 32.08 \(\pm\) 3.88 \\ TGNi+CaRL & 50.86 \(\pm\) 4.83 & 31.01 \(\pm\) 2.78 & 73.34 \(\pm\) 1.99 & 15.43 \(\pm\) 0.93 & 77.42 \(\pm\) 0.80 & 19.57 \(\pm\) 1.29 \\ TGN+SiC & 53.16 \(\pm\) 1.53 & 26.83 \(\pm\) 0.95 & 73.98 \(\pm\) 2.07 & 16.79 \(\pm\) 2.90 & 77.40 \(\pm\) 0.80 & 18.63 \(\pm\) 1.69 \\ \hline TREND & 49.61 \(\pm\) 2.92 & 28.68 \(\pm\) 4.20 & 57.28 \(\pm\) 2.83 & 37.48 \(\pm\) 3.26 & 61.02 \(\pm\) 0.16 & 42.44 \(\pm\) 0.14 \\ TREND+EWC & 53.12 \(\pm\) 3.30 & 25.70 \(\pm\) 3.08 & 65.45 \(\pm\) 4.79 & 26.80 \(\pm\) 4.98 & 62.72 \(\pm\) 1.18 & 40.00 \(\pm\) 2.09 \\ TREND+iCaRL & 52.53 \(\pm\) 3.67 & 30.63 \(\pm\) 0.18 & 69.93 \(\pm\) 5.55 & 15.81 \(\pm\) 7.48 & 74.49 \(\pm\) 0.05 & 23.27 \(\pm\) 0.25 \\ TREND+BiC & 54.22 \(\pm\) 0.56 & 22.42 \(\pm\) 3.15 & 71.15 \(\pm\) 2.42 & 12.78 \(\pm\) 5.12 & 75.13 \(\pm\) 1.06 & 21.70 \(\pm\) 0.63 \\ \hline OTGNet (Ours) & **73.88**\(\pm\) 4.55 & **19.25**\(\pm\) 5.10 & **83.78**\(\pm\) 1.06 & **4.98**\(\pm\) 0.46 & **79.92**\(\pm\) 0.12 & **12.82**\(\pm\) 0.61 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Comparisons (%) of our method with baselines. The bold represents the best in each column.

Figure 4: The changes of average performance (AP) (%) on three datasets with the increased tasks.
this baseline as OTGNet-GBK. As shown in Table 3, OTGNet outperforms OTGNet-w.o.-IB and OTGNet-GBK on the three datasets. This illustrates that it is effective to extract class-agnostic information for addressing the heterophily propagation issue. OTGNet-w.o.-prop generally performs better than OTGNet-w.o.-IB. This tells us that it is inappropriate to directly transfer information between two nodes of different classes. OTGNet-w.o.-prop is inferior to OTGNet, which means that the information is lost if directly dropping the links between nodes of different nodes. An interesting phenomenon is AF score decreases much without using information bottleneck. This indicates that learning better node embeddings by our message passing module is helpful to triad selection.

**Triad Selection Strategy Analysis.** First, we design three variants to study the impact of our triad selection strategy. OTGNet-w.o.-triad means our method does not use any triad (i.e. \(M=0\)). OTGNet-random represents our method selecting triads randomly. OTGNet-w.o.-diversity means our method selecting triads without considering the diversity. As shown in Table 4, The performance of our method decreases much when without using triads, which shows the effectiveness of using triads to prevent catastrophic forgetting. OTGNet achieves better performance than OTGNet-random and OTGNet-w.o.-diversity, indicating the proposed triads selection strategy is effective.

**Evolution Pattern Preservation Analysis.** We study the effectiveness of evolution pattern preservation. OTGNet-w.o.-pattern represents our method without evolution pattern preservation (i.e. \(\rho=0\)). As shown in Table 5, OTGNet has superior performance over OTGNet-w.o.-pattern, which illustrates the evolution pattern preservation is beneficial to memorize the knowledge of old classes.

**Acceleration Performance of Triad Selection.** As stated aforementioned, to speed up the triad selection, we can sort triads \(g_{k}^{c}\) based on the values of \(\mathcal{R}(g_{k}^{c})\), and use top \(K\) triads as the candidate set \(N_{k}^{c}\) for selection. We perform experiments with different \(K\), fixing \(M=10\). Table 6 shows the results. We notice that when using smaller \(K\), the selection time drops quickly but the performance of our model degrades little. This illustrates our acceleration solution is efficient and effective. Besides, the reason for performance dropping is that the total diversities of the triad candidates decreases.

## 5 Conclusion

In this paper, we put forward a general framework, OTGNet, to investigate open temporal graph. We devise a novel message passing mechanism based on information bottleneck to extract class-agnostic knowledge for aggregation, which can address heterophily propagation issue. To overcome catastrophic forgetting, we propose to select representative triads to memorize knowledge of old classes, and design a new value function to realize the selection. Experimental results on three real-world datasets demonstrate the effectiveness of our method.

\begin{table}
\begin{tabular}{l c c c c c c c c} \hline \hline \multirow{2}{*}{Setting} & \multicolumn{2}{c}{Reddit} & \multicolumn{2}{c}{Yelp} & \multicolumn{2}{c}{Taobao} \\ \cline{2-9}  & AP(\(\uparrow\)) & AF(\(\downarrow\)) & Time (h) & AP(\(\uparrow\)) & AF(\(\downarrow\)) & Time (h) & AP(\(\uparrow\)) & AF(\(\downarrow\)) & Time (h) \\ \hline \(K\)=1000 & 73.88 & 19.25 & 1.23 & 83.78 & 4.98 & 0.25 & 79.92 & 12.82 & 1.61 \\ \(K\)=500 & 71.26 & 22.45 & 0.45 & 83.48 & 6.32 & 0.07 & 79.19 & 13.94 & 0.53 \\ \(K\)=200 & 66.83 & 26.88 & 0.07 & 81.86 & 6.87 & 0.02 & 79.14 & 13.73 & 0.10 \\ \(K\)=100 & 66.22 & 28.86 & 0.04 & 78.83 & 10.54 & 0.01 & 78.81 & 14.58 & 0.04 \\ \hline \hline \end{tabular}
\end{table}
Table 6: Results of of of our acceleration solution with different \(K\).
## 6 Acknowledgements

This work was supported by the National Natural Science Foundation of China (NSFC) under Grants 62122013, U2001211.
