Towards Open Temporal Graph Neural Networks
Authors: Kaituo Feng
Changsheng Li
Xiaolu Zhang
JUN ZHOU
Venue: ICLR 2023 notable top 5% (2023)
Keywords: Temporal Graph Neural Networks
Open Temporal Graphs
Class-Incremental Learning

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 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.

Published as a conference paper at ICLR 2023
TOWARDS OPEN TEMPORAL GRAPH NEURAL NET- WORKS
Kaituo Feng
Changsheng Li
Beijing Institute of Technology ka i saituoeeng@@nne i 1, com
Beijing Institute of Technology lcs@bit .dd..cc..
Xiaolu Zhang
Jun Zhou Ant Group
Ant Group
yueyin. www.axxxeaaatincommmm
jun.
ABSTRACT
Graph neural networks (GNNs) for temporal graphs have recently attracted in- creasing attentions, where 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 the time passes by. This will bring two big challenges to the existing temporal GNN methods: (i) How to dynamically propa- gate appropriate information in open temporal graph, where 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 different classes, (ii) How avoid catas- trophic knowledge forgetting over old classes when learning new classes occurred 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 node can disentangled into dels-relevant and class-agnostic one, and thus explore 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. Ex- tensive experiments on three real-world datasets of different domains demonstrate the superiority of our method, compared to the baselines.
class nodes are
message passing
INTRODUCTION
Temporal graph (Nguyen et al. 2018) represents sequence of time-stamped events (c.g. addition
or deletion for edges or nodes) (Rossi al. 2020), which is a popular kind of graph structure in variety of domains such as social networks [Kleibergg] (007). citations networks (Feng et al. [2022). topic communities (Hamilton et al., 2017). etc. For instance, in topic communities, all posts can be modelled 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 al. 2020b 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 effective node embedding by capturing temporal patterns based time-stamped events.
basic assumption among the above methods is that the class set of nodes is always closed, i.e., the class 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 post-to-post graph. When a new topic created 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, node belonging to a new class is often "Corresponding author

---

Published as a conference paper at ICLR 2023
linked to node of old class, as shown in Figure 1 In Figure []] "class 2' is a new class, and "class 1' is an old class. There is link occured at timestamp 44 connecting two nodes 14 and vis, where 04 and its belong different classes. Such connection will lead to sharp contradiction. This is because typical GNNs are prone learn similar embeddings for 04 and Us due to their connection (Xie et al. 2020] /Zhu al. 2020), while we expect the embeddings of v4 and vs to be distinguishable since they belong to dif- ferent classes. We call this dilemma as heterophily propagation. Someone might argue that we can sim- ply drop those links connecting different class nodes. However, this might break the graph structure and lose information. Thus, how and what to transfer be- tween connected nodes of different classes remains a challenge for open temporal graph.
Task
Task
2
14
E4
5
V5
4
L3
t2
6
C8
11
dass 1
class
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. 44 denotes the timestamp the edge is built. The edge occurred at 4 connects V4 and vs (e.g., the same user comments on both post U2 and post U2 in topic communities).
The second problem is the catastrophic forgetting issue. When learning new class in 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.] (2020a); [hhou & Cao (202T) 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 dynamic graphs, called OTGNet. To mitigate the issue of heterophily propagation, we assume the information of 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., (016)) 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 al. 2018 Zignani al., 2014 Huang et al., (0144) point out triad structure striangle-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 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.
learning approach towards open temporal
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-timme dynamic GNNs (Zhou et al. 2018 Goyal et al. 2018 Wang et al.] (020a) and continuous-tim dynamic GNNs (a.k.a. temporal GNNs (gguye et al. 2018)) (Rossi et al. 2020: Trivedi et al., 2019). Discrete-time approaches focus on discrete-time dynamic graph that a collection of static graph snapshots taken at intervals in time, and contains
2

---

Published as a conference paper at ICLR 2023
dynamic information very coarse level. Continuous-tinm approaches study continuous time dynamic graph that represents a sequence of time-stampeds events, and possesses temporal dynamics at finer time granularity. In this paper, 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. 2021
Trivedi et al. 2019) have been proposed. For instance, DyRep (Trivedi et al.] 2019) took the ad vantage
of temporal point process capture fine-grained temporal dynamics. CAW (Wang et al., 202lb)
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 always kept unchanged, neglecting that new classes can be dynamically increased in many real-world applications.
learning have been widely studied in the computer vision community (Li & Hoiem| 2017; Wu et al. (201)). For example, EWC (Kirkpatrick et al.) 2017) proposed to penalize the update of parameters that are significant to previous tasks. iCaRL iLi & Hoiem 2017) maintained 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- non-graph data like images. It is obviously not suitable to directly apply them to graph data.
Class-ineremental learning.
Recently, a few incremental learning works have been proposed for graph data (Wang et al.) 2020a
Zhou & Cao 2021). CoNtinualGNNN (Wang al. 2020a) proposed method for closed discrete-time dynamic graph, and trained the model based on static snapshots. ER-GAT (Zhou & Cao 2022I) 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.
PROPOSED METHOD
3.1 PRELIMINARIES
Notations. Let ((t) = ((t) denote a temporal graph at time-stamp i, where V(t) is the set of existing nodes at f. and (t)) is the set of existing temporal edges f. Each element exj (tx) E {t) represents node and node j are linked at time-stamp (12 < f). Let (t) be the neighbor set of node i at I. We assume x1( denotes the embedding of node at I, where (0) is the initial feature
of node i. Let (() {1, 2.... ..... number of existing classes until time t.
mm()} be the class set of all nodes at I, where m(l) denotes the
Problem formulation. In open temporal graph setting, as new nodes are continually added into the graph, new classes can occur, i.c., the number m(t of classes is increased and thus the class set ('()) is open, rather than closed one like traditional temporal graph. Thus, we formulate our problem as a sequence of
tasks T = (Ti, T2. -...... ................................ TT, .. } in chronological order. Each task Ti contains one or multiple new classes which are never seen in previous tasks {Ti, T2,- ... T In our new problem setting, the goal is to learn an open temporal graph neural network based on current task Tú, expecting our model to not only perform well on current task but also prevent catastrophic forgetting over previous tasks.
3.2 FRAMEWORK
Task Ti-1
Task
As aforementioned, there are two key challenges in open temporal graph learning: heterophily prop- agation and catastrophic forgetting. To address the two challenges, we propose general framework, OTGNet, as illustrated in Figure 2 Our framework mainly includes two modules: A knowledge preser- Figure 2: An illustration of overall architecture. vation 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- agnossic knowledge between different class nodes, which can address the heterophily propagation issue. Next, we will elaborate each module of our framework.
Node Classification
Information Bottleneck Based
Triad Structure Selection
Message Passing
Triad Structure Replay
Module
3

---

Published as a conference paper at ICLR 2023
3.3 KNOWLEDGE PRESERVATION OVER OLD CLASS
When learning new classes based on current task Ti, 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 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 fundamental element of temporal graph and its trtad 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 ] 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 cvolution patterns (Zhou et al., 2018). Motivated by this point, we propose 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 / for all symbols in this section. Without loss of generality, we denote closed triad for class & as gh = (Us, f4), where all of three nodes us Up, Uy belong to class & and Uea Up. 11 are pairwise connected, i.c., (t), (xg(t)), (t) E {(m) and f4, 1 < f1, fm is the last time-stamp of the graph. We denote an open triad for class k as gh = (us, Vpg 0/)) with Up and vg not linked to each other in the last observation of the graph, i.e., eap (t,) eaa E (1m) and egj & {tm)) Assuming S = {gk, 1h.2 .... M. and 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 Si. It is analogous to open triads Sg.
G
E
t
(a) closed triad. (b) open triad.
Figure 3: An illustration for closed triad and open triad.
S% = [gf. "o..::....Rk..
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 estimate the parameter changes of the machine learning model when removing a training sample (Koh & Liang] 2017), we extend the influence function to directly estimate the 'representativeness' of each triad structure without retraining, and propose an objective function as:
d C.K, Oc.0;)
dd de
Ttass
0) (1s
VoL(GE, 0)
de
r=
l==0
= VoL 0) VoLlo
where L represents the loss function, e.g., cross-entropy used in this paper. 0 is the parameter of the model, and G₁ the node set of class k. fe.og the retrained parameter if we upweight three nodes in of by E(E + 0) during training. E is small weight added on the three nodes of the triad Φf in the loss function L. Hg is the Hessian matrix. VoL(ff. 0). V VoL(GR, 0) are the gradients of the loss to of and Gk. respectively. The full derivation of Eq. [ is in Appendix A.2
In Eq. ( Iioss (gE, 0) estimates the influence of the triad Oe on the model performance for class k. The more negative Trose 0) is, the more positive influence on model performance of provides, in other words, the more important of is. Thus, we define the 'representativeness' of triad structure as:
R(gh)
Iioss (gf, 0)
(2)
In order to well preserve the knowledge of old classes, we expect all ge in Sg are important, and propose the following objective function to find S
M
Sc = arg
max A
R(GE.))
During optimizing (3), we only take the triad of, with positive R(gh ) as the candidate, since L. with negative R(g can be thought to be harmful to the model performance. We note that only
4

---

Published as a conference paper at ICLR 2023
optimizing (3) might lead that the selected Jh. have similar functions. Considering this, hope Sg should be not only important but also diverse. To do this, we first define:
.) = و [[ E(gE,)) I 6, Ih E N
(4)
where ((GE,) denotes the average embedding of three vertices in Gh.z- NE denotes the containing all positive closed triads for class k, and ò is similar radius. C(gE,) measures the number of Fi where the distance of ((gh.) and ((gk.) less or equal to 6. To make the selected triads St diverse. we also anticipate that (C(gf.1) ... M1) can cover different triads as many as possible by:
U C(RRW)
S arg
max (of
|Ng
Finally, we combine 5 with 3). and present the final objective function for triad selection as:
UU C(OE,))
St arg
max M
F(SE) arg
max (ot
Σ
R( +
(6)
[.NE
where y is papae-parameter. By (6) 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(SE) satisfies the condition of monotone and submodular. The proof can be found in Appendix AA.] Based on this property, (6) could be solved by a greedy algorithm (Pokutta al. (220)) with an approximation ratio guarantee, by the following Theorem (Krause & Golovin| 2014).
Theorem 1. Assuming our value function F 2 R. is monotone and submodular. If S is an optimal triad set and Sq is triad selected by the greedy algorithm (Pokutta et al. 2020), then F(S)) 2 (1 F(S holds.
Algorithm 1 Representative triad selection
Input: all triads Ng for class k. budget M; Output: representative triad set S%;
1: Initialize St. = 0:
2: while |S < M do
3: u = Newse F(S (uf);
By Theorem 1, we can greedily select closed triads in Algorithm|] [ As aforementioned, the open triad set Sy can be chosen by the same method. The proof of Theorem can be found in Krause & Golovin (201)).
4: = =E=
5: end while
6: return Sj
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, and Ea of class e. Then, for each neighbor node of vs that belongs to class k, we check whether this neighbor node links to Ud- 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 (d2 E& (). where [& is the number of edges between two nodes of class k; and de is the max degree of nodes of class k. When selecting closed triads, finding a closed triad that maximizes the value function takes O (( where [NÇ] is the number of positive closed triads in class k. Thus, it is of order ( ?) for selecting the closed triad set Sg, 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 Ng by only selecting closed triads from of with large values of (o Specifically, we sort the closed triad of based R(gg), and use the top-K ones as the candidate set Ng for selection. The way for selecting open triads is the same.
Triad Structure Replay. After obtaining representative closed and open triad sets, St. and Sg 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 correctly predict the labels of nodes from the selected triad set, and thus use the cross entropy loss Lee for each node in the selected triad set.
Moreover, mentioned above, the triad closure process can capture the evolution pattern of dynamic graph. Thus, we use the link prediction loss Llink to correctly predict the probability whether two nodes are connected based on the closed and open triads, to further preserve knowledge:
1 No No
No Σ log(1 (z (,))),,
Liink =
Σ t=1
(2 2((0))) No
(7)
5

---

Published as a conference paper at ICLR 2023
where Ne.No are the number of closed, open triads respectively, where N: N, N₂ * M. N₂ is the number of old classes. a is the sigmoid function. 2/(() 2 are the embeddings of Up. Ug of the 8th closed triad. H2, (t), # (t) are the embeddings of Up, fg of the hth open triad. Here the closed triads and open triads serve as postive samples and negative samples, respectively.
3.4 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 ! To avoid aggregating conflictive knowledge between nodes of different classes, one intuitive thought is 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:
JIB min I(Z(t), Y) ((()(),, 2(1)
(8)
where 3 is the Lagrange multiplier. I(.,.) denotes the mutual information. X (t); Z(t) the random variables of the node embeddings and class- aggoostic representations at time-stamp t. Y is the random
variable of node label. In this paper, we adopt a two-layer MLP for mapping (() to 2()).
However, directly optimizing (8) is intractable. Thus, we utilize CLUB (Cheng et al. 2020) to
estimate the upper bound of (t), Y) and utilize MINE (Belghazi et al. (018)) estimate the lower bound of I (t),,, X (t)). Thus, the upper bound of our objective could be written as:
JIB LIB E2(2 [log an (vl=(())] - ( [log qu (v)=(())
-3 E (T) (z()),
lox(Ex(xx00))22(00) 2o (z(0)))0)))) (9)
where =(t), =tt), are the instances of (t)., (().. Y respectively. T. X' x 2 R is neural network parametrized by dh. Since p(y]=(t)) unknown, we introduce variational approximation qu (t)) to approximate p(y]=(t)) with parameter By minimizing this upper bound LTp, we can obtain an approximation solution Eq. (8) The derivation of formula (9) is in Appendix A..
is worth noting that (1) is an intermediate variable as the class-agnostic representation of node i. We only use (t) propagate information other nodes having different classes from node i. If one node j has the same class with node i, we still use (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 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:
exp(([>((t)]]
(1h)()))(( (Ib W)) (1((O))((1 W)))
W)))
Ois (1) ElEN((0) exp ((xp(([1(())))))()())))))) [1] (+(
(10)
where & is a time encoding function proposed in TGAT. || represents the concatenation operator. W and W, are two learnt parameter matrices. is the time of the last interaction of node i. L is the time of the last interaction between node and node j. 4 is the time of the last interaction between node and node 1. Note that we adopt different ht(t) from that in the original TGAT, defined as:
(1) [t), (t), y: + y1
y: = 91
(11)
where (t))) is the message produced by neighbor node I E NG(t). If node I and have different classes, we leverage its class-agnostic representation 2x( for information aggregation of node i, otherwise we directly use its embedding (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.

---

Published as a conference paper at ICLR 2023
Finally, update the embedding of node i by aggregating the information from its neighbors:
xx(1)
Σ
ans())aby(0)
(12)
JEN(())
where Wa a learnt parameter matrix for message aggregation.
3.5 OPTIMIZATION
During training, we first optimize the information bottleneck loss LIB. Then, we minimize L = Lee + pLlink. where p the hyper-parameter and Lee 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
Table 1: Dataset Statistics
Reddit
Yelp
Taobao
4.1 EXPERIMENT SETUP
# Nodes
10845
15617
114232
# Edges
216397
56985
455662
Datasets. We construct three real-world datasets
Total classes
18
15
90
evaluate our method: Reddit (Hamilton et al. 2017).
# Timespan
6 months
5 years
days
Yelp (Sankar al., 2020). Taobao (Du et al. 2019).
In Reddit, we construct a post-to-post graph. Specif- ically, we treat posts as nodes and treat the subreddit (topic community) 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 task, where July to December in 2009 are used. In each month, we sample large communities that do not appear in previous months as the graph from 2015 to 2019 in the same way as Reddit. For Taobao dataset, we construct an ttem-to-ited graph in the same way as Reddit in 6-days promotion season of Taobao. Table I summarizes the statistics of these datasets. More information about datasets could be found in Appendix [A.4
Tasks
6
5
Classes per task 3
3
30
# Timespan per task month
year
days
classes. For Yelp dataset, we construct business-to-buse
temporal
Experiment Settings. For each task, 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 al. 2018 Bang al. 202T): ) AP and AF. Average Performance (AP) measures the average performance of 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: ER- GAT (Zhou & Caol 2021), TWC-GAT (Liu et al.) 2021) and ContinualGNN (Wang et al. 2020a). For ER-GAT and GAC, 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. (002)), TGN (Rossi et al. (2020). TREND (Wen & Fang ) and three widely-used class-incremental learning methods in computer vision (EWC (Kirkpatrick et al. 2017). iCaRL (Rebulfi et al. 2017), BiC (Wu ct al. 2019h) as baselines. For our method, we set M as 10 on all the datasets.
4.2 RESULTS AND ANALYSIS
Overall Comparison. As shown in Table 2 our method outperform other methods by a large margin. The reasons follows. For the first three methods, they all based static GNN that 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,
7

---

Published as a conference paper at ICLR 2023
Table 2: Comparisons (%) of our method with basclines. The bold represents the best in each column.
Reddit
Yelp
TaoBao
Method
AP(1)
AF(
AP(1)
AF())
AP(1)
AF())
ContinualGNN
52.17 2.46
23.59 + 5.39
49.73 = 0.27
28.76 + 1.52
58.39 + 0.24
47.03
0.50
ER-GAT
52.03 = 2.59
22.67 + 3.30
62.05 = 0.70
18.91 + 1.09
70.09 + 0.88
23.24 = 0.36
TWC-GAT
52.88 = 0.53
19.60 + 3.64
60.90 = 3.74
16.92 = 0.63
59.91 = 1.71
42.78 = 1.39
TGAT
48.47 +: 1.81
31.03 + 4.48
64.89 + 1.27
27.31
3.99
60.62 + 0.23
43.35 + 0.77
+GA
50.16 2.45
28.27 + 4.00
66.58 3.11
1.75 25.48
1.75
64.03 + 0.62
38,26 = 1.20
TGAT+iCaRL
2.04
27.66 1.11
71.71 2.48
17.56
73.74 + 1.40
23.90 = 2.04
TGAT+BIC
54.61 0.89
2.74
74.73 + 3.54
16.42
74.05 + 0.48
23.27 =
TGN
47.49 0.48
32.06 + 1.91
56.24 + 1.65
41.27
2.30
65.89 + 1.20
36.15 1.55
TGN+EWC
49.45 - 1.45
31.74 + 1.11
60.83 + 3.55
35.73 3.48
68.89 + 2.09
32.08 3.88
TGN+iCaRL
50.86 1: 4.83
31.01 1 2.78
73.34 + 1.99
15.43
0.93
77.42 + 0,80
19.57 - 1.29
TGN+BiC
53.16 1 1.53
1.53
26.83 1 0.95
73.98 1: 2.07
16.79 1 2.90
77.40 1 0.80
18.63 1 1.69
TREND
49.61 0661:220 2.92
28.68 + 4.20
57.28 + 2.83
37.48 + 3.26
61.02 + 0.16
42.44 = 0.14
TREND+EWC
$3.12
25.70 3.08
65.45 4.79
26.80 + 4.98
62.72 + 1.18
40.00 = 2.09
TREND+iCARL
52.53 3.67
30.63
0.18
69.93 5.55
15.81
= 7.48
74.49 + 0.05
23.27 0.25
TREND+BiC
54.22
0.56
22.42
4 3.15
71.15 + 2.42
12.78 4: 5.12
75.13 + 1.06
21.70 = 0.63
OTGNet (Ours)
73.88
4.55
19.25 + 5.10
83.78 +
4.98 0.46
79.92 + 0.12
12.82 0.61
TWC-GAT
ER-GAT Reddit
ContinunCCNN
TGAT BIC
TGN
TREND Taobao
OTGNet
Yelp
Average Performance
100
100
100
60
40
task leaming sequence Figure 4: The changes of average performance (AP) (%) on three datasets with the increased tasks.
task learning sequence
3 task fearning sequence
2
TGAT and TREND, the phenomenon of catastrophic forgetting is alleviative. 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 Table we do not report the results of the other two incremental learning based methods. addition, the curves of OTGNett smoother that those of other methods, which indicates 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. OTGNNet-wo.-IIB represents method directly transferring the embeddings of neighbor nodes instead of class-agnostic rep- resentations. OTGNet-w.o. -prp 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
Table Ablation study of our proposed information bottleneck based propagation mechanism.
Reddit
Yelp
TaoBao
Setting
AP(1)
AF(()
AP(T)
AF(()
AP(1)
AF(J)
54.10 + 2.01
34,00 + 1.63
76.93 + 5.14
14.96 + 5,61
79.00 = 0.37
13.41 + 0.57
OTGNet-w.o.propp
54.67 + 2.05
28.73
+ 2.63
75.67
+ 1.69
12.87
+ 1.19
79.07 = 0.02
14.48
+ 0.34
OTGNet-GBK
58.79 + 1.08
25.22
2.22
77.03
+ 2.99
9.79
+ 1.15
77.73
15.49
0.34
OTGNet
73.88 4.55
19.25
+ 5.10
83.78
+ 1.06
4.98 + 0.46
79.92 - 0.12
12.82
+ 0.61
8

---

Published as a conference paper at ICLR 2023
Table 4: Results of triad selection strategy on the three datasets.
Reddit
Yelp
TaoBao
Setting
AP(1)
AF(
AP(1)
AF())
AP(1)
AF())
OTGNet- w.o-trad
60.81 4.46 34.94 4.73 69.28 1.73
23.79 + 1.75 67.05 = 0.44 31.44 0,41
OTGNet-
69.66 + 3,81
23.24 3.83 78.76 - 2.62
9.19 - 1.65 79.09 = 0.36
13.89 + 0.45
OTGNet-ww w.o. -iiversiyy 71.06 + 5.73 22.96 + 6.91 80.76
2.60
9.91
+ 3,83 78.84 = 0.46
13.87 + 1.18
OTGNet
73.88 + 4.55 19.25 = 5.10 83.78 1.06 4.98
+ 0.46 79.92 = 0.12 12.82 0.61
Table 5: Results of evolution pattern preservation on the three datasets.
Reddit
Yelp
TaoBao
Setting
AP(t)
AF())
AP(1)
AF(J)
AP(()
AF(()
OTGteet-wo--pateem 70.23 + 5.56 23.10 + 7.44 81.44 + 1.38
6.97 3.10
79.01 + 0.19 14.05 + 0.46
OTGNet
73.88 + 4.55 19.25 + 5.10 83.78 + 1.06 4.98 + 0.46 79.92 + 0.12 12.82 + 0.61
Table 6: Results of of our acceleration solution with different K. Reddit
Yelp
Taobao
AP(1)
AF(()
Time (h)
AP(T)
AF(J)
Time (h)
AP(1)
AF(L)
Time (h)
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
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. better than OTGNet-w.o,-IBB This tells us that it is inappropriate to directly transfer information between two nodes of different classes. OTGNet-w.o. oropppp 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.
generally performs
Triad Selection Strategy Analysis. First, we design three variants study the impact of our triad selection strategy. OTGNet-w.o.. -.o-tr-wwo.-rriad means our method does not use any triad (i.e. M = 0). OTGNet-random represents our method selecting triads randomly. OTGNet-w.o-ddivee w.vv-iiriid means our method selecting triads without considering the diversity. As shown in Table 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-randon and "GGeett...-dvversii indicating the proposed triads selection strategy is effective.
Evolution Pattern Preservation Analysis. We study the effectiveness of evolution pattern preserva- tion. O. patttrr represents our method without evolution pattern preservation (i.e. P = O). As shown in Table OTGNet has superior performance over OT.Nettw.o.- -.o.ttttte,,, which illustrates the evolution pattern preservation beneficial to memorize the knowledge of old classes.
Acceleaatoo Performance of Triad Selection. As stated aforementioned, to speed up the triad selection, we can sort triads of based on the values of R(g)), and use top triads as the candidate set N for selection. We perform experiments with different K, fixing M = 10. Table 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.
CONCLUSION
In this paper, we put forward a general framework, OTGNet, to investigate open temporal graph. We devise 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.

---

Published as a conference paper at ICLR 2023
6 ACKNOWLEDGEMENTS
This work was supported by the National Natural Science Foundation of China (NSFC) under Grants 62122013, U2001211.
REFERENCES
Alexander A Alemi, Ian Fischer, Joshua V Dillon, and Kevin Murphy. Deep variational information bottleneck. arXiv preprint arXiv:1612.00410, 2016.
Jihwan Bang, Heesu Kim, YoungJoon Yoo, Jung- Woo Ha, and Jonghyun Choi. Rainbow memory: Continual learning with a memory of diverse samples. IEEE Conference on Computer Vision and Pattern Recognition, pp. 8218-8227, 2021.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In International Conference on Machine Learning, pp. 531-540. PMLR, 2018.
Arslan Chaudhry, Puneet K Dokania, Thalaiyasingam Ajanthan, and Philip HS Torr. Riemannian walk for incremental learning: Understanding forgetting and intransigence. European Conference on Computer Vision, pp. 532-547, 2018.
Pengyu Cheng, Weituo Hao, Shuyang Dai, Jiachang Liu, Zhe Gan, and Lawrence Carin. Club: A contrastive log- ratio upper bound of mutual information. In International Conference on Machine Learning, pp. 1779-1788. PMLR, 2020.
R Dennis Cook and Sanford Weisberg. Characterizations of empirical influence function for detecting influential cases in regression. 'eechnometrics, 22(4):495-500 1980.
Monroe D Donsker and SR Srinivasa Varadhan. Asymptotics for the wiener sausage. Communications on Pure and Applied Mathematics, 28(4):525-563) 1975.
Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei Zhang. Gbk- gnn: Gated bi-kernel graph neural networks for modeling both homophily and heterophily. In Proceedings of the ACM Web Conference 2022, pp. 1550-1558, 2022.
Zhengxiao Du, Xiaowei Wang, Hongxia Yang, Jingren Zhou, and Jie Tang. Sequential scenario- specific meta learner for online recommendation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2895-2904, 2019.
Kaituo Feng, Changsheng Li, Ye Yuan, and Guoren Wang. Freekd: Free-direction knowledge distillation for graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 357-366, 2022.
Palash Goyal, Nitin Kamra, Xinran He, and Yan Liu. Dyngem: Deep embedding method for dynamic graphs. arXiv preprint 1805. 1273, 2018.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Annual Conference on Neural Information Processing Systems, 30, 2017.
Hong Huang, Jie Tang, Sen Wu, Lu Liu, and Xiaoming Fu. Mining triadic closure patterns in social networks. In Proceedings of the 23rd international conference on World wide web, pp. 499-504, 2014.
Mohsen Kian. Operator jensen inequality for superquadratic functions. Linear Algebra and its Applications, 456:82 87, 2014.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho. Agnieszka Grabska- Barwinska, et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114 (13):3521-3526, 2017.
10

---

Published as a conference paper at ICLR 2023
Jon M Kleinberg. Challenges in mining social network data: processes, privacy, and paradoxes. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 4-5, 2007.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning, pp. 1885-1894. PMLR, 2017.
Andreas Krause and Daniel Golovin. Submodular function maximization. Tractability, 3:71-104, 2014.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in
temporal interaction networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 1269-1278, 2019.
Hanjie Li, Changsheng Li, Kaituo Feng, Ye Yuan, Guoren Wang, and Hongyuan Zha. Robust knowledge adaptation for dynamic graph neural networks. arXiv preprint wrxiv:2207.1083: 2022.
Zhizhong Li and Derek Hoiem. Learning without forgetting. IEEE transactions on patlern analysis and machine intelligence, 40(12):2935-22 2947, 2017.
Huihui Liu, Yiding Yang, and Xinchao Wang. Overcoming catastrophic forgetting in graph neural networks. In AAAI Conference on Artificial Intelligence, volume 35, pp. 8653 1553-8661,,11 2021.
Giang Hoang Nguyen, John Boaz Lee, Ryan Rossi, Nesreen K Ahmed, Eunyee Koh, and Sungchul Kim. Continuous time dynamic network embeddings. In Companion Proceedings of the The Web Conference 2018, pp. 969-976, 2018.
Sebastian Pokutta, Mohit Singh, and Alfredo Torrico. On the unreasonable effectiveness of the greedy algorithm: Greedy adapts sharpness. In International Conference Machine Learning, pp- 7772-7782. PMLR, 2020.
Sylvestre-Alve Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampert. icarl: Incremental classifier and representation learning. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 2001-2010, 2017.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006.10637 2020.
Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural rep- resentation learning on dynamic graphs via self-attention networks. In Proceedings of the 13th international conference on web search and data mining, pp. 519-527, 2020.
Xiaoyu Tao, Xiaopeng Hong, Xinyuan Chang, Songlin Dong, Xing Wei, and Yihong Gong. Few-shot classenne learning. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 12183-12192, 2020.
Naftali Tishby, Fernando Pereira, and William Bialek. The information bottleneck method. arXiv preprint physics/0004057, 2000.
Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning representations over dynamic graphs. International Conference on Learning Representations, 2019.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008
Zhibin Wan, Changqing Zhang, Pengfei Zhu, and Qinghua Hu. Multi-view information-bottleneee representation learning. In AAAI Conference on Artificial Intelligence, volume 35, pp. 10085- 10092, 2021.
Junshan Wang, Guojie Song, Yi Wu, and Liang Wang. Streaming graph neural networks via continual learning. In ACM International Conference on Information and Knowledge Management, pp. 1515-1524, 2020a.
11

---

Published as a conference paper at ICLR 2023
Xiaoyang Wang. Yao Ma, Yiqi Wang, Wei Jin, Xin Wang, Jiliang Tang, Caiyan Jia, and Jian Yu. Traffic flow prediction via spatial temporal graph neural network. In Proceedings of The Web Conference 2020, pp. 1082-1092, 2020b.
Xuhong Wang. Ding Lyu, Mengjian Li, Yang Xia, Qi Yang, Xinwen Wang, Xinguang Wang, Ping Cui, Yupu Yang, Bowen Sun, et al. Apan: Asynchronous propagation attention network for real-time temporal graph embedding. In Proceedings of the 2021 International Conference on Management of Data, pp.
2021a.
Yanbang Wang. Ye Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning temporal networks via causal anonymous walks. arXiv preprint 4rX5v:2101.05974, 2021b.
Zhihao Wen and Yuan Fang. Trend: Temporal event and node dynamics for graph representation learning. In Proceedings of the ACM Web Conference 2022, pp. 1159-1169, 2022.
Yue Wu, Yinpeng Chen, Lijuan Wang. Yuancheng Ye, Zicheng Liu, Yandong Guo, and Yun Fu. Large scale incremental learning. IEEE Conference on Computer Vision and Patter Recognition, pp. 374-382, 2019.
Yiging Xie, Sha Li, Carl Yang. Raymond Chi Wing Wong, and Jiawei Han. When do gnns work: Understanding and improving neighborhood aggregation. In International Joint Conference on Artificial Intelligence, 2020.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive representa- tion learning on temporal graphs. arXiv preprint arXiv:2002.07962, 2020.
Fan Zhou and Chengtai Cao. Overcoming catastrophic forgetting in graph neural networks with experience replay. arXiv preprint arXiv:2003. 09908, 2021.
Lekui Zhou, Yang Yang, Xiang Ren, Fei Wu, and Yueting Zhuang. Dynamic network embedding by modeling triadic closure process. In AAAI Conference Artificial Intelligence, volume 32, 2018.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Annual Conference on Neural Information Processing Systems, 33:7793-7804, 2020.
Matteo Zignani, Sabrina Gaito, Gian Paolo Rossi, Xiaohan Zhao Haitao Zheng, and Ben Y Zhao. Link and triadic closure delay: Temporal metrics for social network dynamics. In Eighth International AAAI Conference on Weblogs and Social Media, 2014.
12

---

Published as a conference paper at ICLR 2023
A
APPENDIX
A.1 DERIVATION OF OUR INFORMATION BOTTLENECK OBJECTIVE
Our message passing mechanism is motivated by traditional information bottleneck (Alemi et al. 2016 Tishby et al. 2000). The objective of traditional information bottleneck is maxz [ Y) 31(2, X), which attempts to maximize the mutual information between label and latent represen- tation Z, and minimize the mutual information between input feature X and latent representation Z. Different from that, we intend to extract class- agssosiic information from node embeddings. Thus, we aim to minimize the mutual information between node label Y and class- -lass-agnostic representation (t)), and maximize the mutual information between input embedding X X() and class-agnostic representa- tion Zt). Our objective could be written as: JIB min z(t) T(Z(t), Y) 3T(2, (()) First, give a proof of the upper bound of I (t)), Y), motivated by Cheng et al. 2020). Let Letub Y)
r)) log (t))) (p()()) (2)r))oog p(y)=((((()))))) Let Iclub ()) ((Z(t)) Y), then
we have:
d=(0)dgp(=(0)))))ogg (ogp)))))))))))))))))))))))))))) d d=(()(z(00) / dyp(y)log (ogp(v)=(()
dz(()ddp((=(1)))) log plul=(1)
p(v)
- dz(t)p(z(()) f
dyplu) (ogpllz(t))
dyp(y) log - dyp(v) / Logt))ll))))))p()())))))
(yply)(oogp(c dz(t)p(=(t) logr(vl=(t)).
(13)
Since (og(-) (-) is concave function, according Jensen's Inequality (Kian 2014), we have:
log p(y)
(14)
Then, we have:
dyplu)(logp(w) - -a do(0))(((0)) 2 0.
(15)
Thus, we derive the upper bound of I(Z(tt, Y):
I(Z(1), Y) S Ietub (Z(1), (otuo =o 1 Po (16)
Since (t))=(t)) is unknown, we introduce a variational approximation distribution qu ())) to
approximate (t)) following Cheng et al. (2020).
Next, we give a proof to the lower bound of [[X (t), Ztt)), based on Belghazi al. (018). According
to Donsker-Varan representation (Donsker & Varadhan 1975). we know:
((),,, (()) = KL (X4))XXX))2()))xxxX())))))00
SuPr.n-RExxxeu
- -og(
(17)
where Ω = X' x 2 is the input space. Let F be any class of functions : - R. we have:
(L(p(X(t)) Z(t), p(X(t))p(Z(t)) 2 E T log -oo
(18)
We could choose J to be the family of functions To X Z E parameterized by neural network
//:
KT (1)) (())))))))(((())))(())))) 200p 1 (19)
Thus, we have:
((X()), Z())) Tminne (()),(()) Supp (ogg))))))o(((oooooeeeeeo (o((paxconnrzzooee))) (20)
13

---

According Cook & Weisberg 1980), we know that the influence of upweighting could be dO Published as a conference paper at ICLR 2023
Therefore, could derive upper bound of JIB:
JIB S LIB = Lotub - (X Z(t)
= Sy (v)
-
(21)
In order to minimize JrB, we attempt to minimize its upper bound, i.e., L,B, and utilize the Monte Carlo sampling to approximate the expectations in LıB, motivated by (Wan et al. 2021 Alemi et al. 2016). Therefore. the final loss function of LIB can expressed as:
LIB
log qu (xrl2((()))
log (x)g)(((())
Sal
Saa
iESa
jESa
B
1
(2)()(t))2)(())
loog
(22)
SSa
Saa
S
jESa
where Sa is batch of nodes and |Sal is the size of Sa. xy (4), 2;()) are the embedding, the class-
agnostic representation of node respectively at time-stamp t. Yr the label of node i.
A.2 DERIVATION OF TRIAD INFLUENCE FUNCTION
In this section, we prove that our triad influence function Toss (gf, 0) could estimate the influence of the triad of on the model performance for class k: The triad influence function Ttsss (gf 0) is defined as:
Iooes(gE 0) Ve 0) "1 Vo 0),
(23)
where 0 the parameter of the model and G& is the training node of class k. He is the Hessian matrix. VoL(gh, 0). VoL(G,, 0) are the gradient of loss to Jh. and Gs, respectively.
The basic idea of the influence function (Cook& Weisberg 1980 Koh Liang 2017) to estimate the parameter change if a training sample is upweighted by some small E (E + 0). Thus, we add small weight on three nodes of the triad of in the loss function L(0). The new loss function could be written as:
Le.gg (0) = arg min
Σ I(,,
+
Σ 1(v, VE
VEG
(24)
L(K,, 0) el(gE, 0),
where I(u, f) is the loss of node v. With the new loss function, the parameter of model changed to &2.0z = arg min Le,og(0),
evaluated by de
==0
Since the new loss function condition:
24 is minimized by d..gg examine the first-order optimality
VeL(Gr, VV 9).
(25)
Then, since we have dz.ng + 0 as + 0, we perform Taylor expansion on the right-hand side of Eq. (55 and the higher order infinitesimal o(0 0) terms are dropped
0 [Vo((G,, + 0) [V3C + - 0).
(26)
From Eq. 26 we could derive that
(27)
Because 9 minimizes L(GR. 8), VoL(GE, 0) equals 0. By dropping the higher order infinitesimal o(s) terms, we have:
0g 0 m -)
(28)
14

---

Published as a conference paper at ICLR 2023
We denote the He ViL(GR 0), and thus have:
i d..gE 0 Vo 0).
(29)
Then, we could estimate the change of parameters influenced by triad as follows:
d 20
0 00.0E
-E H VoLigh 0)
d
(30)
==0
H
VoLlgh) 8).
Finally, we could derive the triad influence function Tinss (1k, 0) by the chain rule:
cl (c.0f))
ddc.gq
Tloss (1. 0)
-Vo(GG, 0)
de
de
(31)
==0 = -ooo 0) H VoL(o 0).
1==0
A.3 PROOF OF MONOTONICITY AND SUBMODULARITY Our proposed value function is defined as:
Σ VoL(GR, " 0) + 10 Coe,
F(SE)=
(32)
LIVE
where Cop. = ( ( )12 S E E No and Ng is the set containing all triads with positive R. As stated before, finding fixed size set Sy (Sg No. that maximizes F(S)) is NP-hard due to the combinatorial complexity. Thus, we first prove that our value function F is monotone and submodular. Then our optimization problem could be solved by greedy algorithm
with an approximation ratio guarantee according to Krause & Golovin 2014))
Definition 1. (Monotonicity) function f 2 + IR monotone if for VA C B N, it holds that F(A) < F(B).
Lemma 1. Our value function F in Eq. (32 monotone.
Proof. We define two triad sets A, B that satisfy A ACBEN Let A = F(B) - F(A). We have:
A Σ VeL(Gr, 0)T H₂ VoLlge 0)
Σ
Hg VeL(GR, 7)H VoC(ge
En
EA
UU UU EB Cog.!!
UUBE,EA Cog.!!
[Nal
[Nvl
VoL(GE, 8)T H
E
Vellgh. 8) Σ VoL(gh 0))
En
DR.EA
UBB Coc.1
C Coe.l
+
[Nol
[Nol
Un Coc.el
= VoL(Gr, () TH
Σ
VeLlgh. 0)
NNol
[Nol
ET
I EB CoE,
UUR Coi.! [Nel
1 EA
UUR.EAA Coe
2
= 0.
[e
[Ncl
Nel
Thus, have:
A F(B) F(A) 20.
(33)
+ F(A) S F(B).
(34)
n
15

---

Published as a conference paper at ICLR 2023
Definition 2. (Submodularity) A function f 2 + R is submodular if for AA C B S N and Vr E B, it holds that F(AU [x)) - F(4) 2 F(BU - F(B).
Lemma 2. Our value function F in Eq. (32) is submodular.
Proof. We define two triad sets A, B that satisfy A S B N Let = BYA Define A (F(AU {x}) F(A)) - (F(B (x+) F(B)). Then we have:
A GK, 0) 'HH
Vollok 0)
-V 01+ (B. U U EB CE
VoLlgk 0)
-Vol(sk 0))
EAU(()
EA
EAUR)) CoR.
1U D0 Com.e!
1U 1U Co...!
) (35)
LIVEl A = VoL(GE, 0) "
1.N
Σ
VoLlih, 0)
Σ (oLlsgk 0))
U UUEE,AAHH) Cog.l
1U9i, EA CoE.!
UB Coi
1U9 CoR.l! UB
) (36)
[AN I0 EAULE Cor..!
IIVEl
l
UURR,EA CoE.A
IU U 96, EBB(E) Coa.!!
UU COR
(37)
IINEl
NN
I UU EAUEE) C
UURREA CoE.A!
U 1U Caj.e!
1U EAUT Cakes
INE
ING
NN
[Ng
1 (IC U CO
U Cot,))
U CoN..)
No EA
EE,EA
- U CO
U
U
CoE 21
U Coe, ( U
Co.. I.. (38)
ET
E(w)
ET
For convenience, we denote Ug EQ Cos. = Cg. We have:
A
(1C2
UC
(o) |c*| |CA UC (T) UC | + UC))))
|Ngll
1
(1C*
[ctza] - (())) |C + 12 +
|Ng
NNg
+12 n (
h n( + + UCT)
[Ng
1
[Ng] (-IC1) - |ct + [C n c [C] C n Ciry C(()
+ +ICA| + |c7 - -c nc
(IC) Cin - iCa n Ciry (c
0.
(39)
Then, we can derive:
A = -
2.
(40)
+ F(AU(()) - -FU
(41)
16

---

Published as a conference paper at ICLR 2023
A.4 DATASET DETAILS
Reddit Dataset Reddit is a large platform of topic communities where people could write and upload their posts to share their opinions. For the Reddit dataset D we construct a post-to-post graph, similar to Hamilloon et al. (2017). We omit the top 20 largest communities, because they are large and generic default communities, which could skew the class distribution (Hamilton al. 2017). From the rest of communities, in each month we sample 3 largest communities that doesn't I appear in previous months as new classes for each task. We take the data from July to November in 2009 and construct 6 tasks based on the selected data. In the graph, the posts are regarded as nodes and their corresponding communities are regarded as node labels. When a user comments a post at time the temporal edges at timestamp / will be built, connecting this post to other posts this user has commented within a week. We initialize the feature representation of a node by averaging 300- dineeinnniionl GloVe word embeddings of all comments in this post, following Hamilton et al. (0177)
Yelp Dataset Yelp is large business review website where people could upload their reviews for commenting business, and find their interested business by others' reviews. For the Yelp datase we construct bessines--t-business temporal graph, in the same way as Reddit. Specifically, we take the data from 2015 to 2019, and treat the data in each year as a task, thus forming 5 tasks in total. In each year, we sample 3 largest business categories as three classes in each task. Note that the business categories in each task have never occurred in previous tasks. We regard each business as node and set the business's 's category as its node label. The temporal edge will be formed, once a user reviews the corresponding two businesses within a month. We initialize the feature representation for each node by averaging 300-dimensional Glo Ve word embeddings of all reviews for this business.
Taobao Dataset Taobao large online shopping platform where items (products) could be viewed and purchased by people online. For the Taobao datase 3 Du et al. 2019), we construct an item-to-item graph, in the same way as Reddit. The data in the Taobao dataset is 6-days promotion season of Taobao in 2018. We set the time duration for each task as 2 days. In each two days, we take the top 30 largest item categories according to the number of items as the new classes for this task. The categories in each task have never occurred in previous tasks. We regard the items as nodes and take the categories of items as the node labels. The temporal edge will be built if a user purchases two corresponding items in the promotion season. We use the 128- 22-dimensional embedding provided by the original dataset as the initial feature of the node.
A.5 PSEUDO-CODE OF PROPOSED METHOD
We provide the pseudo-code of our training procedure, as shown in Algorithm 2 When learning task Tr we input the interactions in current task and triads of previous tasks together into our proposed message passing framework. All nodes in current interactions and previous triads are used to calculate node classification loss for training. The closed triads and open triads serve as positive and negative samples to preserve evolution patterns, respectively. After learning task Tú, we select representative triads for the classes in T, and then begin to learn task T Note that our algorithm does not guarantee that the selected triads must be connected with the nodes in the new task. This is because the selected triads play two roles in connected with the nodes in a new task, it will propagate knowledge among these nodes by extracting class-agnostic representations; on the other hand, triads are used to preserve the knowledge of old classes, so as to avoid catastrophic knowledge forgetting when learning new classes. Even though the selected triad does connect with the nodes in the new task, think it still is important for learning old classes by simultaneously considering both importance and diversity.
method: one hand, when the nodes in the triads
A.6 IMPLEMENTATION DETAILS
We perform our experiments using GeForce RTX 3090 Ti GPU. We use the Adam optimizer for training with learning rate 77 0.0001 on the Reddit dataset, learning rate 1 0.005 on the Yclp
hhtts:://fills. wwwp:psssssti.oooccctttoooooooot http://wwwww.llp.oom/mttc https:/tiaccii.aliyye
17

---

end for Published as a conference paper at ICLR 2023
Algorithm 2 OTGNet: Open Temporal Graph Neural Networks
Input: task number L, last time-stamp t, interaction set ((),, node label set )/(t) = node initial feature (0), epochs Ne, memory budget per class M, trade-off parameter p; Output: prediction of node classes;
m())
1: Initialize node embeddings;
2: Initialize triad memory buffer S 0:
3: for each task Ti from Ti Tr. do
4: for each epoch from to N₂ do
5: for each batch in epoch do let Н be the set containing all interactions in batch b;
6:
7:
Ti * TI then
8:
let Hrre be the set containing the interactions for all triads in S;
9:
H = H.HeH prei
10:
end if
extract class-agnostic embeddings for all interactive nodes and their neighbors H: propagate message for all interactive nodes in H; calculate node classification loss Lee for all interactive nodes in H;
12:
13:
14:
let L Leei
15:
Ti + TI then calculate link prediction loss Lrink for all triads in S: L= Lee + phiinki
17:
18:
end if
19:
minimize the information bottleneck loss LIB: minimize the training loss C:
21:
end for end for
22:
23:
for each class k in task T: do
24:
select representative closed triad set S for class by Algorithm I; select representative open triad set Sg for class by Algorithm 1; 5 S Sg U
25:
26:
27:
end for
28:
for each task Ty from Ti to T; do
29:
evaluate the performance of our model on the unseen test data of Ty;
30:
end for
datasets and learning rate 0.001 on the Taobao datasets. For all baselines and our method, we train each new task until convergence, and then evaluate the performance the model on current task and all previous tasks. For the Reddit dataset and the Yelp dataset, we train each task 500 epochs. For the Taobao dataset, we train each task 100 epochs. We set the dropout rate 0.5 on all the datasets. The node classification head is a two-layer MLP with hidden size 128. The selected triad pairs per class M is set to 10 on all datasets. The sub-network extracting class-agnostic information is a two-layer MI_P with hidden size 100. Note that we do not use a whole graph in the forward pass computation. For replaying the triads, we sample 5 neighbors of cach node in the triad for forward propagation, motivated by the sampling strategy in TGAT and TGN. For the nodes the current new task, we also sample 5 neighbor nodes (maybe from old class nodes) for each node to aggregate the neighborhood information.
A.7 ADDITIONAL EXPERIMENTS
Forgetting Analysis of Different Task Numbers. We study the average forgetting (AF) changes of different methods along with the increased tasks. As stated in the main body of this paper, AF measures the decreasing extent of model performance on previous tasks compared to the best ones. Note that AF does not count the last task since the forgetting for the last task has not yet happened. As shown in Figure 5 AF our method is generally smaller than that of other methods. This indicates that our method generally suffers from less catastrophic forgetting than other methods.
18

---

Published as a conference paper at ICLR 2023
TWC-GAT
ER.GAT Reddit
ContinualGNN
TGAT+ BIC
TGN+BIC
TREND+ BIC
OTGNet
Yelp
Taobao
Average Forgetting
50
50
50
40
40
40
30
20
20
20
10
10
10
0
3
task learning sequence
task learning sequence
task learning sequence
Figure 5:
The changes of average forgetting (AF) (%) on three datasets with the increased tasks.
0.0
0.5
-1.9
training
-1.5
-2.0
-2.5
3.0
100
150
200
250
300
50
100
150
200
250
300
epochs
epochs
(a) Training loss
(h) Information bottleneck loss LIB
Figure 6: Convergence analysis. A new task is added for every 100 epochs.
Convergence Analysis. We analyze the convergence of our method. We plot the loss curves (including the total training loss and the information bottleneck loss LıB on the largest dataset, Taobao. As shown in Figure 6 our method can be eventually convergent when learning for each task.
Sensitivity Analysis of M. We analyze the influence of the number M of selected triads when fixing K = 1000. As shown in Figure (b), it could be observed that when fix K 1000, our method obtains good performance when M 2 10. This because with relatively large K, we could select not only important but also diverse triads to preserve knowledge for achieving good performance. Thus, we set M 10 throughout the experiment.
Sensitivity Analysis of p. We analyze the sensitiveness of p. is the hyper-parameter on the link prediction loss for evolution pattern preservation. As shown in Figure 8 (b(),, we observe that our method is not sensitive to p in relatively large range.
Sensitivity Analysis of We analyze the sensitivity of in our method. Recall that is trade-off parameter for balancing the contributions between diversity and importance when selecting representative triads. As shown in Figure 9 our method is not sensitive to y in relatively large range.
100
30
M =
M 10
M 15
20
M 20
20
80
10
70
60
Reddit
Yelp
Taobao
Reddit
Yelp
Taobao
(a) AP with varying M
(b) AF with varying
Figure The sensitivity of M our method on three datasets
19

---

Published as a conference paper at ICLR 2023
100
30
0=
p= 0.5
0.7
0.9
20
80
70
Reddit
Yelp
Taobao
Reddit
Yelp
Taobao
(a) AP with varying
(b) AF with varying
Figure 8: The sensitivity of p in our method on three datasets
100
30
y= 12
16 y=
y=
16
y=
90
y= 24
y= 24
20
10
60
Reddit
Yelp
Taobao
Reddit
Yelp
Taobao
(a) with varying
(b) with varying 7
Figure 9: The sensitivity of y in our method on three datasets.
100
30
0.1
B = 0.1
0.2
8 0.2
0.3
B 0.3
90
= 0,4
B
80
10
70
60
Reddit
Yelp
Taobao
Reddit
Yelp
Taobao
(a) AP with varying
(b) AF with varying
Figure 10: The sensitivity of in our method on three datasets
20

---

Published as a conference paper at ICLR 2023
30
100
6=0.5
155 o= 2.0
2.0
20
10
70
60 Reddit
0
Yelp
Taobao
Reddit
Yelp
Taobao
(a) AP with varying
(h) AF with varying
Figure 11: The sensitivity of 8 in method three datasets
Sensitivity Analysis of We analyze the sensitivity of in our method. the Lagrange multiplier in the objective of information bottleneck. As shown in Figure 10 we observe that our method has stable performance when changing 3 in certain range.
Sensitivity Analysis of 8. We further analyze the sensitivity of d in method. å is hyper- parameter for measuring the diversity of triad set. As shown in Figure [T. our method is not sensitive in a relatively large range.
A.8 AP AND AF FOR EACH TASK.
Here we provide the AP and AF metric for each task of our method and two baselines (TGAT+BiC, TGN+BiC) which generally perform well among all baselines. As shown in Table our method generally outperforms two baselines for most tasks.
Table AP and AF for each task the Reddit dataset.
Task
Task 2
Task
Task 4
Task
Task 6
Method
AP
AF
AP
AF
AP
AF
AP
AF
AP
AF
AP
AF
TGAT+BiC
50.52
23.96
47.18
23.59
42.31
21.15
63.03
26.86
46.18
31.53
78.46
TGN+BiC
52.26
22.22
56.34
9.15
35.34
29.09
63.03
30.05
31.85
43.63
80.15
OTGNet
61.02
15.80
71.83
20.25
39.30
45.43
83.38
13.16
91.72
1.59
95.97
Table 8: AP and AF for each task on the Yelp dataset.
Task
Task 2
Task
Task 4
Task 5
Method
AP
AF
AP
AF
AP
AF
AP
AF
AP
AF
TGAT+BIC
71.61
9.76
78.89
9.63
73.68
21.84
62.23
24.46
87, 87.25
TGN+BiC
55.50
23.07
79.63
7.04
74.47
22.63
72.83
14.40
87.45
OTGNet
76.38
0.26
88.89
0.74
83.95
10.79
79.62
8.15
90.08
Table 9: AP and AF for each task on the Taobao dataset.
Task
Task 2
Task
Method AP
AF
AP
AF
AP
AF
TGAT+BIC
68.82
22.69
63.16
23.86
90.15
TGN+BiC
74.23
17.62
67.96
19.65
90.00
OTGNet
77.62
12.86
72.81
12.80
89.35
21

---

Published as a conference paper at ICLR 2023
Table 10: Running time (hours) comparison with baselines.
Reddit
Yelp
Taobao
Method
AP
AF
Time (h)
AP
AF
Time (h)
AP
AF
Time (h)
TGAT+BIC
54.61
25.42
5.05
74.73
16.42
3.03
74.05
23.27
5.82
TGN+BiC
53.16
26.83
5.81
73.98
16.79
3.17
77.40
18.63
6.23
TGAT-retrain
75.86
3.71
26.31
87.64
0.61
10.07
83.35
0.78
32.75
TGN-retrain
77.41
3.34
31.58
80.83
3.47
10.80
81.63
3.64
35.65
OTGNet
73.88
19.25
6.78
83.78
4.98
3.73
79.92
12.82
7.81
A.9 RUNNING TIME ANALYSIS
When new classes occur, if we combine all data of old classes with the data new classes for retraining, the computational complexities will be sharply increased, and be affordable. Here, compare the running time of our method with the retraining methods (TGAT-retrain, TGN-retrain) and two baselines (IGAT+BiC, TGN+BiC) which generally perform well among bascline methods. For the retraining methods, we use all data of old tasks for training when learning new tasks.
As shown in in Table TO the running time of method is comparable the incremental learning baselines +TGAT+BiC, TGN+BiC), while our model outperforms them on AP and AF metric with large margin. For the retraining methods (TGAT-retrain, TGN-retrain), we can see the running time is increased by several times. In real-world applications, new classes might frequently occur. we use all history data for training once new class occurs, the time consuming could be unaffordable. Note that their Average Forgetting (AF) are better than our model. This is because they use all training data for learning each time, and thus can avoid forgetting.
A.10 LIMITATIONS AND FUTURE WORKS
The quadratic time complexity of triad selection is a limitation of our method. Although only considering partial triads could be efficient, the performance of our model would be degraded to some extent. How develop more efficient and effective algorithm for representative triad selection is our future work. For example, we could design a hierarchical selection policy to reduce the time complexity, develop divide-and-conquer method for efficient triad selection. What's more, can design better practical approximations to the theoretical optimal solution of our value function to select representative triads.
A.11 VISUALIZATIONS
(a) OTGNet-w.o.i. -BB
(b) OTGNet
Figure 12: t-SNE visualization of learned node embeddings on Reddit when task finished. Different colors denote different classes.
22

---

Published as a conference paper at ICLR 2023
(a) OTGNet-w.O.-IB
(b) OTGNet
Figure 13: t-SNE visualization of learned node embeddings on Reddit after new task is added. Different colors denote different classes. The new task contains new classes.
To qualitatively demonstrate the effectiveness of our class-agnostic representations, we adopt t-SNE (Van der Maaten Hinton 2008) visualize the learned node embeddings of our OTGNet. For comparison, we also visualize the node embeddings of OTGNet-w.o.-ID (i.c.. OTGNet directly transferring the embeddings of neighbor nodes instead of class-agnostic representations). Figure T2 shows the results of their learned node embeddings on Reddit when task is finished, and Figure 13 demonstrates the results after a new task is added. We can clearly observe that OTGNet possesses better representation ability by considering dlas-aggostic representations.
23


Reviews:
[{"review_id": "oaLONpHbakd", "reviewer": "Reviewer_KnTc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focusing on continuous open temporal graph where new nodes and new target node labels will join with time going on. This field is lack of study, and this paper proposes OTGNet which is far better than similar works.", "summary_of_the_review": "This paper focues on continuous open temporal graph task which is lack of study, and make a concrete contribution to the field with OTGNet which is empirically far better than similar baselines.", "strength_and_weaknesses": "## Strength\n\n- This paper focues on continuous open temporal graph which is lack of formal study in previous works.\n- This paper proposes OTGNet which is empirically far better than similar works.\n\n## Weakness\n\nSome statements need to be improved for better understanding.\n\n- The definition of $I_{loss}$ need to be improved. For example, upweight by $\\epsilon$ need to be formally expanded. I understand that $\\epsilon$ is the extra weighted classification loss only for traidic nodes only after reading the appendix.\n- Will it be possible that Algorithm 1 select triadics that are not connected with any node in current batch or task? I think those triadics are meaningless. If Algorithm 1 can avoid this, how it is guaranteed? I do not see any step in Algorithm 1 to avoid this.\n- Class-agnostic representation $Z(t)$ need to be clarified. How to really compute $L_{IB}$? I think it is infeasible to compute any expection value in the formula.\n- Is neural network method the only way to get $Z(t)$? I think this optimization is quite classic, and may have non-parametric approximation. Can you confirm that there is no other approximation?\n\nBesides, I have a minor concern of Algorithm 2:\n\n- For every task, you will select new important triadics $S_k$ for each class and update them in the memory. Thus the triadic buckect $S$ will indeed grow without restriction. Is there any way that you can limit the maximum size of $S$? If so, how will this restriction hurts the performance?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ZokVEz971_", "reviewer": "Reviewer_WeDg", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper focuses on learning GNNs on open temporal graph where new nodes with novel classes are also added to the graph. The proposed method solves two major issues that existing temporal GNN methods have under this setting: learning with added heterophily and catastrophic forgetting. To solve the catastrophic forgetting, a data selection process motivated by the fluence function is considered which is defined to maximize the representativeness of the selections. The author proposes an information bottleneck based loss function to encourage the model to learn the class agnostic representations. Experimentations on real-world benchmark suggests this algorithm works with state of art temporal GNN and performs favorably.", "summary_of_the_review": "This paper provides a neat and novel solution to the open temporal graph, a setting is of great practical value but not actively researched. The algorithm's correctness is proved both theoretically and empirically. ", "strength_and_weaknesses": "Strength:\n1. The problem of learning open temporal graph is of great practical value as in many applications where graphs are updated consistently with both new and old node types. The algorithm proposed in the paper clearly improves the state of art temporal GNN algorithms under this setting. \n2. The proposed methods are well motivated, and are supported with both theoretical and empirical results. \n3. The proposed algorithm is very generalizable. It works with basically any temporal GNN model with no or little modifications.\n\nWeakness:\n1. The experimentation process needs further elaboration, especially on how the baseline models are trained and tuned. For example, there might be trade-off between AP and AF depending on how many epochs the model trains on the new task.\n2. While the loss function encourage class-agnostic representation, to what extend the learned representation is class-agnostic can be better depicted besides the ablation study measured by model performances. For example, suppose we cluster the embeddings, will the clusters correlate with classes?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "WQo_p10bjW5", "reviewer": "Reviewer_FhGE", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes OTGNet to tackle the problem of continual learning/class-incremental learning on graphs. OTGNet consists of two components. The first component is an open/close triad selection and replay method to avoid catastrophic forgetting of existing knowledge. The second component is an information bottleneck module to decouple class-related knowledge from class-agnostic knowledge, and use the class-agnostic knowledge for propagation between nodes from new classes and existing classes. It is designed to avoid over-smoothing between existing classes and new classes. The authors perform experiments on real-world class-incremental settings. The proposed OTGNet outperforms various baselines of continual learning on graphs. ", "summary_of_the_review": "Overall, I think this paper proposes a novel and insightful solution to an important problem, with solid experimental evaluations. I recommend accepting the paper. ", "strength_and_weaknesses": "Strengths: \n- The problem of class-incremental GNN learning is valid and interesting. Dynamics and new classes are indeed problems in real-world graph learning. \n- The observation that nodes from existing classes influence nodes from new classes due to homophily is a unique and interesting perspective. It is also shown in the experiments that this indeed poses challenges and affects the results. \n- The designed methods seem novel and sound. Selecting important triads for replay to alleviate forgetting makes sense. Using influence functions to approximate the importance of triads is interesting. \n- The experimental results seem very good. The improvements over existing works are significant. The ablation studies are extensive enough to demonstrate the effects of individual components. \n\nWeaknesses and Questions: \n- Some notations and words can be revised to better describe the methods. For example, $log$ should be $\\log$, $exp$ should be $\\exp$, $sup$ should be $\\sup$, 'representative' should be 'representativeness'. \n- Some details of the proposed method are not very clearly described. I list several unclear points. \n    - On measuring the representativeness. We know that nodes in a graph influences the learned model in two ways, both in forward propagation (i.e. neighborhood aggregation) and backward propagation (i.e. model optimization via the loss). As far as I can see, the influence function in Eqn. 1 can only capture the latter one, i.e. whether a node appears in the loss, but not the former one, i.e. whether the node propagates its features to neighboring nodes. \n    - Intuitively, the scores $\\mathcal{R}(g_k^c)$ should influence each other. For example, suppose $i, j, k$ and $i, j, m$ are both close triads of class $k$, $i, j$ are both important nodes (e.g. hubs with high degrees) while $j, m$ are not. It is likely that both triads will get high scores. However, it is often sufficient to select only one of them (as only $i, j$ are important), i.e. with the presence of $i, j, k$, the score of $i, j, m$ will decrease. Is my understanding correct? If yes, how can OTGNet address for the case? \n    - In the triad structure replay, it is said that 'we will replay these triads from old classes when learning new classes'. However, it is not clear how will nodes that are not in selected triads be dealt with. Specifically, will they still participate in the forward propagation? If they are dropped, there will be missing auxiliary information (e.g. nodes in the selected triads will have missing neighbors). If they are not, the training cost is still high (since a whole graph participates in forward computation). Please clarify that. \n    - In Eqn. 10, 11, 12, it seems that $x_i(t), z_i(t)$ are not related to the layer. Does it imply that OTGNet only supports one layer of TGAT? \n- I appreciate the extensiveness of experiments with the following minor questions. \n    - I suggest some visualization or case study on the class agnostic embeddings $z$ and $x$ to better illustrate the necessity of learning $Z$. \n    - In Table 6, changing $K$ from 1000 to 100 leads to a significant performance drop. However, in Figure 7, it shows that the performance stabilizes with only $M=20$, which means that only 20 triads per class is enough for OTGNet to work. This seems counter-intuitive. From my understanding, it indicates that the triads with high $\\mathcal{R}$ (top $K$) do not necessarily lead to a good selection. Is that correct? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "62GjKmX7k_a", "reviewer": "Reviewer_Riiz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a new task in temporal networks and with new methods. The proposed problem is related to the new class appearing at different times. \n\nThe authors claimed there are two challenges for the current temporal network: 1) How to dynamically propagate appropriate information in an open temporal graph, where new class nodes are often linked to old class nodes. This indicates that temporal graphs are usually homophily. 2) How to avoid catastrophic knowledge forgetting over old classes when learning new classes occurred in temporal graphs. No previous temporal network model includes a class-incremental learning setting.\n\nTo handle these two challenges, the authors proposed an information bottleneck-based message-passing framework, assuming that the information of a node can be disentangled into a class-relevant and class-agnostic one.", "summary_of_the_review": "Overall, I think this paper is borderline paper. This paper proposed a novel task. It focused more on the class-incremental learning problem. The tasks and proposed methods all focused on this topic. The temporal network setting is more like a specific task. The paper also proposed some new techniques to solve this problem but these techniques are mostly from papers from other domains. The performance is not solid enough, with only 2 baselines that are only focused on the temporal network (can't solve either class incremental problems or heterophilic graph problems). ", "strength_and_weaknesses": "Strength:\n\nThis paper proposed a framework to handle the class-incremental task in the temporal graph. The Triad Structure Selection is interesting. By using the influence function, it can select the important triangles. The task is novel and interesting. To accelerate the algorithm, the authors also apply a greedy result by showing that the value function F is monotone and submodular. This is intuitive. The experiments also shows that the model compared with TGN and TGAT have a better result, the ablation result shows that all the module works well. The experiments in the appendix show that the model can learn the class-agnostic knowledge and is able to mitigate the catastrophic forgetting problems. The ablation study is solid.\n\nWeaknesses: I have the following questions:\n\nFirst, the paper mentioned the heterophily setting in the temporal graph, which can be one main issue. However, in previous research, people found that the heterophily indicates that usually, GNN(such as vanilla GCN) can't work, but the traditional pagerank-based algorithms(APPNP) or other models which have a more powerful aggregator method(such as GCNII, GGCN, or other attention-based models, which implicitly handle the heterophily by a learning-based aggregator) perform well in these heterophily tasks. I think this kind of model should also be a baseline (although I understand the setting is a temporal graph and new coming tasks, so maybe the authors can first ignore the temporal information. ). Moreover, the baselines are not enough, both TGN and TGAT are baselines 2 years ago. Plenty of temporal network models are proposed and should be compared. \n\nSecondly, the time complexity of choosing triads is unscalable. If the testing set is large, or the graph itself is large, the algorithm can't work in a limited time. However, for temporal graphs, we usually have more edges due to the time domain. Some possible work like Causal Anonymous Walk may somehow solve this issue by random walk. And these methods also have the potential to represent more complex motives instead of triangles.\n\n[1] Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks\n[2] Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%