summaries: This work empirically evaluates the sliding-window strategy for training GNNs with temporal graphs. One may cast the temporal nature of the graph data in an online setting, under which the change of the graph structure as well as the variation of the classes cause distribution shift. The authors conduct a series of experiments to show that the sliding-window strategy is as effective as using the entire historical data for training.

summaries: This paper proposes a paradigm which speeds up the training time of GNNs while not compromising too much performance. The method adopts a layerwise training procedure. In particular, the authors inject a loss function at each layer while storing and fixing the feed-forward values of its previous layer. The training is then carried out along all layers parallelly, which allows the updating of paradigms to be decoupled and is not applicable in previous works. A further improvement (lazy-update) by not updating the feed-forward values of each layer is used to reduce the training time.

summaries: This work studies the problem of online or incremental learning in temporal graphs (dynamic networks), and more precisely, whether past data can be discarded/ignored without losing predictive accuracy under the assumption that there is the presence of a distribution shift. This question has been essentially investigated over the years in various contexts, e.g., relational learning and classification in dynamic or time-evolving networks. It is also completely obvious that forgetting older data, especially under the assumption of a distribution shift, makes sense and is the correct thing to do. This is exactly what has been done in time-series forecasting for decades. The problem formulation is unclear and can be more precisely defined and motivated appropriately. This needs to be fixed. Are the class labels of a node changing over time, so if a node has label A at time t, then at time t+1 it could have label B, etc. This doesn’t seem true, as it seems the class labels of the nodes are “static”, which is unrealistic in many cases. How are the graph snapshots created? How was the timespan selected? What does every time step represent (1 hour, 5 minutes, etc.)?  Also, are the node features changing over time? This doesn’t seem true, but if this is the case, then it is unclear why this would be the case in practice (it would be great to provide some motivation for this, or an example application or problem where this may be true). There are many assumptions that make this problem unrealistic. Furthermore, there have even been works that study the dynamic node classification problem previously, see [1-2] below.

abstractText: Online learning of graph neural networks (GNNs) faces the challenges of distribution shift and ever gbv rowing and changing training data, when temporal graphs evolve over time. This makes it inefficient to train over the complete graph whenever new data arrives. Deleting old data at some point in time may be preferable to maintain a good performance and to account for distribution shift. We systematically analyze these issues by incrementally training and evaluating GNNs in a sliding window over temporal graphs. We experiment with three representative GNN architectures and two scalable GNN techniques, on three new datasets. In our experiments, the GNNs face the challenge that new vertices, edges, and even classes appear and disappear over time. Our results show that no more than 50% of the GNN’s receptive field is necessary to retain at least 95% accuracy compared to training over a full graph. In most cases, i. e., 14 out 18 experiments, we even observe that a temporal window of size 1 is sufficient to retain at least 90%.

authors:
Aleksandar Bojchevski
Johannes Klicpera
Bryan Perozzi
Amol Kapoor
Martin Blais
Benedek Rózemberczki
Michal Lukasik
Stephan Günnemann

title: Scaling graph neural networks with approximate pagerank

venue: In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD

authors:
Xavier Bresson
Thomas Laurent

title: Residual gated graph convnets

authors:
Jianfei Chen
Jun Zhu
Le Song

title: Stochastic training of graph convolutional networks with variance reduction

venue: In ICML,

authors:
Wei-Lin Chiang
Xuanqing Liu
Si Si
Yang Li
Samy Bengio
Cho-Jui Hsieh

title: Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks

venue: In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD

authors:
da Xu
chuanwei ruan
evren korpeoglu
sushant kumar
kannan achan

title: Inductive representation learning on temporal graphs

venue: In International Conference on Learning Representations,

authors:
Vijay Prakash Dwivedi
Chaitanya K. Joshi
Thomas Laurent
Yoshua Bengio
Xavier Bresson

title: Benchmarking graph neural networks

authors:
D. Ersan
C. Nishioka
A. Scherp

title: Comparison of machine learning methods for financial time series forecasting at the examples of over 10 years of daily and hourly data of dax 30 and s&p 500

venue: J Comput Soc Sc,

authors:
Matthias Fey
Jan E. Lenssen

title: Fast graph representation learning with PyTorch Geometric

venue: In ICLR Workshop on Representation Learning on Graphs and Manifolds,

authors:
Benjamin Fish
Rajmonda S Caceres

title: A task-driven approach to time scale detection in dynamic networks

venue: In Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG’17). http://www. mlgworkshop. org/2017/paper/MLG2017 paper 17

authors:
Xavier Glorot
Yoshua Bengio

title: Understanding the difficulty of training deep feedforward neural networks

venue: In AISTATS 2010,

authors:
Palash Goyal
Nitin Kamra
Xinran He
Yan Liu

title: Dyngem: Deep embedding method for dynamic graphs

authors:
Palash Goyal
Sujit Rokka Chhetri
Arquimedes Canedo

title: dyngraph2vec: Capturing network dynamics using dynamic graph representation learning

venue: Knowl.-Based Syst.,

authors:
William L. Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive representation learning on large graphs

venue: In NeurIPS,

authors:
Wen-bing Huang
Tong Zhang
Yu Rong
Junzhou Huang

title: Adaptive sampling towards fast graph representation learning

authors:
Diederik P. Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

authors:
Thomas N. Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

venue: In ICLR,

authors:
Srijan Kumar
Xikun Zhang
Jure Leskovec

title: Learning dynamic embeddings from temporal interactions

venue: arXiv preprint arXiv:1812.02289,

authors:
John Boaz Lee
Giang Nguyen
Ryan A Rossi
Nesreen K Ahmed
Eunyee Koh
Sungchul Kim

title: Dynamic node embeddings from edge streams

venue: IEEE Transactions on Emerging Topics in Computational Intelligence,

authors:
Franco Manessi
Alessandro Rozza
Mario Manzo

title: Dynamic graph convolutional networks

venue: Pattern Recognition,

authors:
T. Melnychuk
A. Wirsich
C. Schultz

title: Effects of university-industry collaborations in basic research on different stages of pharmaceutical new product development

venue: In Innovation and Product Development Management Conference,

authors:
Federico Monti
Davide Boscaini
Jonathan Masci
Emanuele Rodolà
Jan Svoboda
Michael M. Bronstein

title: Geometric deep learning on graphs and manifolds using mixture model cnns

venue: In CVPR. IEEE Computer Society,

title: Power laws, pareto distributions and zipf’s law

venue: Contemporary physics,

authors:
Giang Hoang Nguyen
John Boaz Lee
Ryan A. Rossi
Nesreen K. Ahmed
Eunyee Koh
Sungchul Kim

title: Continuous-time dynamic network embeddings

venue: In WWW (Companion Volume),

authors:
Aldo Pareja
Giacomo Domeniconi
Jie Chen
Tengfei Ma
Toyotaro Suzumura
Hiroki Kanezashi
Tim Kaler
Tao B. Schardl
Charles E. Leiserson

title: Evolvegcn: Evolving graph convolutional networks for dynamic graphs

venue: In AAAI,

authors:
Hogun Park
John Moore
Jennifer Neville

title: Deep dynamic relational classifiers: Exploiting dynamic neighborhoods in complex networks

venue: In Proceedings of MAISoN Workshop in International Conference on Web Search and Data Mining (WSDM),

authors:
Emanuele Rossi
Ben Chamberlain
Fabrizio Frasca
Davide Eynard
Federico Monti
Michael Bronstein

title: Temporal graph networks for deep learning on dynamic graphs

venue: arXiv preprint arXiv:2006.10637,

authors:
Emanuele Rossi
Fabrizio Frasca
Ben Chamberlain
Davide Eynard
Michael Bronstein
Federico Monti

title: Sign: Scalable inception graph neural networks. 2020b

authors:
Ryan A. Rossi
Jennifer Neville

title: Time-evolving relational classification and ensemble methods

venue: Lecture Notes in Computer Science,

authors:
Gerard Salton
Christopher Buckley

title: Term-weighting approaches in automatic text retrieval

venue: Information processing & management,

authors:
Aravind Sankar
Yanhong Wu
Liang Gou
Wei Zhang
Hao Yang

title: Dysat: Deep neural representation learning on dynamic graphs via self-attention networks

venue: In WSDM,

authors:
Youngjoo Seo
Michaël Defferrard
Pierre Vandergheynst
Xavier Bresson

title: Structured sequence modeling with graph convolutional recurrent networks

venue: In ICONIP. Springer,

authors:
Jie Tang
Jing Zhang
Limin Yao
Juanzi Li
Li Zhang
Zhong Su

title: Arnetminer: Extraction and mining of academic social networks

venue: In KDD

authors:
Rakshit Trivedi
Hanjun Dai
Yichen Wang
Le Song

title: Know-evolve: Deep temporal reasoning for dynamic knowledge graphs

authors:
Rakshit Trivedi
Mehrdad Farajtabar
Prasenjeet Biswal
Hongyuan Zha

title: Dyrep: Learning representations over dynamic graphs

authors:
Petar Veličković
Guillem Cucurull
Arantxa Casanova
Adriana Romero
Pietro Liò
Yoshua Bengio

title: Graph attention networks

authors:
Minjie Wang
Lingfan Yu
Da Zheng
Quan Gan
Yu Gai
Zihao Ye
Mufei Li
Jinjing Zhou
Qi Huang
Chao Ma

title: Deep graph library: Towards efficient and scalable deep learning on graphs

venue: arXiv preprint arXiv:1909.01315,

authors:
Felix Wu
Tianyi Zhang
Amauri H. Souza Jr.
Christopher Fifty
Tao Yu
Kilian Q. Weinberger

title: Simplifying graph convolutional networks

authors:
Keyulu Xu
Chengtao Li
Yonglong Tian
Tomohiro Sonobe
Ken-ichi Kawarabayashi
Stefanie Jegelka

title: Representation learning on graphs with jumping knowledge

authors:
Keyulu Xu
Weihua Hu
Jure Leskovec
Stefanie Jegelka

title: How powerful are graph neural networks

authors:
Zhitao Ying
Jiaxuan You
Christopher Morris
Xiang Ren
William L. Hamilton
Jure Leskovec

title: Hierarchical graph representation learning with differentiable pooling

venue: NeurIPS,

authors:
Hanqing Zeng
Hongkuan Zhou
Ajitesh Srivastava
Rajgopal Kannan
Viktor K. Prasanna

title: Graphsaint: Graph sampling based inductive learning method

venue: In 8th International Conference on Learning Representations,

heading: 1 INTRODUCTION

text:
Training of Graph Neural Networks (GNNs) on temporal graphs has become a hot topic. Recent works include combining GNNs with recurrent modules (Seo et al., 2018; Manessi et al., 2020; Sankar et al., 2020; Pareja et al., 2020) and vertex embeddings as a function of time to cope with continuous-time temporal graphs (da Xu et al., 2020; Rossi et al., 2020a). Concurrently, other approaches have been proposed to improve the scalability of GNNs. Those include sampling-based techniques (Chiang et al., 2019; Zeng et al., 2020) and shifting expensive neighborhood aggregation into pre-processing (Wu et al., 2019; Rossi et al., 2020b) or post-processing (Bojchevski et al., 2020).
However, there are further fundamental issues with temporal graphs that are not properly answered yet. First, as new vertices and edges appear (and disappear) over time, so can new classes. This results in a distribution shift, which is particularly challenging in an online setting, as there is no finite, a-priori known set of classes that can be used for training and it is not known when a new class appears. Second, scalable techniques for GNNs address the increased size of the graph, but always operate on the entire graph and thus on the entire temporal duration the graph spans. However, training on the entire history of a temporal graph (even in the context of scaling techniques like sampling (Chiang et al., 2019; Zeng et al., 2020)) may actually not be needed to perform tasks like vertex classification. Thus, it is important to investigate if, at some point in time, one can actually “intentionally forget” old data and still retain the same predictive power for the given task. In fact, is has been observed in other tasks such as stock-market prediction that too much history can even be counterproductive (Ersan et al., 2020).
Proposed Solution and Research Questions While we do not suggest to use an entirely new GNN architecture, we propose to adapt existing GNN architectures and scalable GNN techniques to the problem of distribution shift in temporal graphs. In essence, we propose a new evaluation procedure for online learning on the basis of the distribution of temporal differences, which assesses the nature of how vertices are connected in a temporal graph by enumerating the temporal differences of connected vertices along k-hop paths. This information is crucial for balancing between capturing the distribution shift while having sufficient vertices within the GNN’s receptive field.
In summary, the central question we aim to answer is, whether we can intentionally forget old data without losing predictive power in an online learning scenario under presence of distribution shift.
We simulate this scenario by applying temporal windows of different sizes over the temporal graph, as illustrated in Figure 1. The window size c resembles how much history of the temporal graph is used for training, or with other words: which information we forget. In this example, data older than t − 2 is ignored. We evaluate the accuracy of representative GNN architectures and scalable GNN techniques trained on the temporal window, against training on the entire timeline of the graph (full history). We evaluate the models by classifying the vertices at time step t, before we advance to the next time step.
To answer the research question, we break it down into four specific questions Q1 to Q4, each answered in a separate experiment. For Q1: Distribution Shift under Static vs Incremental Training, we verify that incremental training is necessary to account for distribution shift, compared to using a once-trained, static model. Extending from Q1, we investigate in Q2: Training with Warm vs Cold Restarts whether it is preferable to reuse model parameters from the previous time step (warm start) or restart with newly initialized parameters at each time step (cold start). In Q3: Incremental Training on Different Window Sizes, we answer the question what influence different choices for the window sizes have, i. e., how far do we need to look into the past such that a GNN trained on the window is still competitive to a model trained on the full graph. Question Q4 extends Q3 by considering Q4: Incremental Training with Scalable GNN Methods, i. e., how scalable GNN approaches compare to using the full history of the temporal graph and to which extent scaling techniques can be applied on top of the temporal window.
New Datasets To enable an analysis with a controlled extent of distribution shift, we contribute three newly compiled temporal graph datasets based on scientific publications: two citation graphs based on DBLP and one co-authorship graph based on Web of Science. To determine candidate window sizes, we contribute a new measure to compute the distribution of temporal differences within the k-hop neighborhood of each vertex, where k corresponds to the number of GNN layers. We select the 25th, 50th, and 75th percentiles of this distribution as candidate window sizes. This results in window sizes of 1, 3, and 6 time steps for the two DBLP datasets, and 1, 4, 8 for the Web of Science dataset.
Results We select three representative GNN architectures: GraphSAGE-Mean (Hamilton et al., 2017), graph attention networks (Veličković et al., 2018) and jumping knowledge networks (Xu et al., 2018) along with graph-agnostic multi-layer perceptrons. As scalable GNN techniques, we consider GraphSAINT (Zeng et al., 2020) as well as simplified GCNs (Wu et al., 2019). The results of our experiments show that already with a small window size of 3 or 4 time steps, GNNs achieve at least 95% accuracy compared to using the full graph. With window sizes of 6 or 8, 99% accuracy can be retained. With a window size of 1, for almost all experiments, a relative accuracy of no less than 90% could be retained, compared to models trained on the full graph. Furthermore, our experiments confirm that incremental training is necessary to account for distribution shift in temporal graphs and we show that both reinitialization strategies are viable and differ only marginally, when the learning rates are tuned accordingly. Surprisingly, simplified GCNs perform notably well on the most challenging dataset DBLP-hard and are only outperformed by GraphSAGE-Mean.
We outline the related work below. We provide a problem formalization and selection of GNNs for our experiments in Section 3. We describe the experimental apparatus and datasets in Section 4. The results of our experiments are reported in Section 5 and discussed in Section 6, before we conclude.

heading: 2 RELATED WORK

text:
In Rossi & Neville (2012), the authors distinguish between tasks where the predicted attribute is static or changing over time. The dynamic graph problem is set up in a way that vertex and edge features may change over time and that edges may appear and disappear. This is conceptually different as it assumes a fixed vertex set, whereas in our case, the vertex set is changing over time. Furthermore, the predicted attribute is static in our case because it will not change after the respective vertex has appeared. Several recent works follow this setup and assume a fixed vertex set (Trivedi et al., 2017; Seo et al., 2018; Kumar et al., 2018; Trivedi et al., 2019; Manessi et al., 2020; Sankar et al., 2020).
In Park et al. (2017), the authors use vertex features concatenated with the adjacency vector and apply 1D-convolution. The experiments comprise link prediction and user state prediction. 1Dconvolution on the time axis can be regarded as a sliding window. However, the paper does not consider new classes during the evaluation time frame and does not analyze how much past training data would be required for up-training.
In Fish & Caceres (2017), the authors aim to find the optimal window size, given a dataset, a task, and a model. They treat the window size as a hyperparameter and propose an optimization algorithm which requires multiple runs of the model. This might be rather expensive. Furthermore, the study does not supply insights on how much predictive power can be preserved when selecting a nearoptimal but much smaller, and thus more efficient, window size.
CTDNE (Nguyen et al., 2018) is an embedding method for continuous-time graphs introducing temporal random walks. This approach considers graphs with featureless vertices with the objective to learn a meaningful/useful vertex embedding. In a recent extension of CTDNE (Lee et al., 2020), the method is applied to edge streams via up-training of the embedding. Comparing this approach to our work, we find that we have another task (discrete-time online vertex classification vs continuoustime online vertex embedding), consider a different type of graph (attributed vs featureless), and face different challenges (adaption to new classes). Nevertheless, it would be an interesting direction of future work to apply our experimental procedure to (streaming) CTDNE.
For discrete-time dynamic graphs involving new vertices, Goyal et al. (2018) proposes DynGEM as an autoencoder-like approach that jointly minimize reconstruction loss between t and t + 1 and embedding distance between connected vertices. In Dyngraph2vec (Goyal et al., 2020), the authors extend this approach by additional variants such as recurrent decoders.
EvolveGCN (Pareja et al., 2020) and T-GAT (da Xu et al., 2020) are both inductive approaches designed for attributed temporal graphs. EvolveGCN predicts the parameters of a GCN with an RNN by tying the RNN output or hidden state to the GCN parameters. T-GAT introduces a selfattention mechanism on the time axis. These approaches can cope with newly appearing vertices and are able to predict different labels for the same node at different times. They both require a sequence of graph snapshots for training. When new classes appear, these sequence-based models would need to be retrained. In our setting with limited window sizes, the sequence of snapshots within a window, i.e. the data available for retraining, might become very short: down to only one snapshot in the extreme case. Furthermore, these approaches focus on predicting future edges or predicting a label for each vertex at each time step. Therefore, the models serve a different purpose compared to the setting that we face, in which the label of each vertex is fixed. For these two reasons, we have focused on adapting and evaluating more efficient, static architectures as well as scalable GNN techniques, while leaving the adaption of T-GAT and EvolveGCN as future work.
To summarize, most works on dynamic graphs assume a fixed vertex set, while considering dynamics within the vertex/edge features, and/or the edges themselves. Inductive approaches such as EvolveGCN and T-GAT do allow new nodes. CTDNE can deal with new nodes via up-training. Previous work on finding optimal window sizes proposes a hyperparameter tuning algorithm. However, none of these works specifically analyzes the problem of new classes appearing over time and how much past training data is necessary, or how few is enough, to maintain good predictive power.

heading: 3 PROBLEM FORMALIZATION AND SELECTED METHODS

text:
Problem Formalization We consider a vertex-labeled temporal graph Gt = (Vt, Et) with vertices Vt and edges Et, provided by a sequence of snapshots ordered by t ∈ N. Thus, Vt is the (finite) set of vertices that are in the graph at time step t, and Et the corresponding set of edges at time step t. Furthermore, we define the set of all vertices V ::= ⋃ i∈N Vi and all edges E ::= ⋃ i∈NEi, i. e., G = (V,E). Let tsmin : V → N be a function that returns for each vertex v ∈ V the timestamp at which the vertex was first added to the graph, i. e., tsmin : v 7→ min{i ∈ N|v ∈ Vi}. Finally, for each vertex v ∈ V we have a feature vector Xv ∈ RD, where D is the number of vertex features, and a class label yv ∈ C with C being the global set of classes C ::= ⋃ i∈N Ci.
In each time step t, previously unseen vertices and edges and even new classes may appear as illustrated in Figure 1. For these temporal graphs, we investigate training graph neural networks for the vertex classification task, i. e., assigning class labels y to previously unseen vertices based on vertex attributes X and connections to other vertices via edges. We denote the history of vertices and edges we take into account as the temporal window. The temporal window spans a range of multiple time steps, which we denote as the temporal window size c.
Selected Graph Neural Networks Several works have been proposed that combine GNNs with recurrent neural networks to capture temporal dynamics (Seo et al., 2018; Manessi et al., 2020; Sankar et al., 2020; Pareja et al., 2020). Other works focus on continuous-time temporal graphs (da Xu et al., 2020; Rossi et al., 2020a). Our work is orthogonal to those works as we focus on the distribution shift of temporal graphs and the question if and when old data can be deleted without sacrificing predictive power. In the following, we introduce and motivate our choice of representative GNN architectures as well as scalable GNN techniques for our experiments.
Dwivedi et al. (2020) have introduced a benchmarking framework to re-evaluate several recent GNN variants. Dwivedi et al. distinguish between isotropic and anisotropic GNN architectures. In isotropic GNNs, all edges are treated equally. Apart from graph convolutional networks (Kipf & Welling, 2017), examples of isotropic GNNs are GraphSAGE-mean (Hamilton et al., 2017), DiffPool (Ying et al., 2018), and GIN (Xu et al., 2019). In anisotropic GNNs, the weights for edges are computed dynamically. Instances of anisotropic GNNs include graph attention networks (Veličković et al., 2018), GatedGCN (Bresson & Laurent, 2017) and MoNet (Monti et al., 2017).
We select GraphSAGE-Mean (GS-Mean) (Hamilton et al., 2017) as a representative for isotropic GNNs because its special treatment of the vertices’ self-information has shown to be beneficial (Dwivedi et al., 2020). The representations from self-connections are concatenated to averaged neighbors’ representations before multiplying the parameters. In GS-Mean, the procedure to obtain representations in layer l+ 1 for vertex i is given by the equations ĥl+1i = h l i|| 1degi ∑ j∈N (i) h l j and hl+1i = σ(U lĥl+1i ), where N (i) is the set of adjacent vertices to vertex i, U l are the parameters of layer l, σ is a non-linear activation function, and ·||· is the concatenation. We select Graph Attention Networks (GATs) by (Veličković et al., 2018) as representative for the class of anisotropic GNNs. In GATs, representations in layer l + 1 for vertex i are computed as follows: ĥl+1i = w l ih l i + ∑ j∈N (i) w l ijh l j and h l+1 i = σ(U
lĥl+1i ), where the edge weights wij and self-connection weightswi are computed by a self-attention mechanism based on the representations hi and hj , i. e., the softmax of a(U lhi||U lhj) over edges, where a is a single-layer neural network with LeakyReLU activation.
Scaling Graph Neural Networks to Large Graphs Several approaches have been proposed to scale GNNs to large graphs. In general, these approaches fall into two categories: sampling either locally (Hamilton et al., 2017; Huang et al., 2018), or globally (Chiang et al., 2019; Zeng et al., 2020), and separating neighborhood aggregation from the neural network component (Wu et al., 2019; Rossi et al., 2020b; Bojchevski et al., 2020).
From both categories, we select one representative for our experiments. We use GraphSAINT (Zeng et al., 2020) as state-of-the-art sampling technique along with simplified GCNs (Wu et al., 2019) as a representative for shifting the neighborhood aggregation into a preprocessing step.
Simplified GCN (Wu et al., 2019) is a scalable variant of Graph Convolutional Networks (Kipf & Welling, 2017) that admits regular mini-batch sampling. Simplified GCN removes nonlinearities and collapses consecutive weight matrices into a single one. Thus, simplified GCN can be described by the equation ŶSGC = softmax(SKXΘ), where the parameter K has a similar effect as the number of layers in a regular GCN, S is the normalized adjacency matrix and Θ is the weight matrix. Instead of using multiple layers, the k-hop neighbourhood is computed by SK , which can be precomputed. This makes Simplified GCN efficient to compute, while not necessarily harming the performance.
In GraphSAINT (Zeng et al., 2020), entire subgraphs are sampled for training GNNs. Subgraph sampling introduces a bias which is counteracted by normalization coefficients for the loss function. The authors propose different sampling methods: vertex sampling, edge sampling, and random-walk sampling. We use the best-performing random-walk sampling for our experiments. The underlying GNN is exchangeable, yet the authors suggest to use Jumping Knowledge networks (JKNets) (Xu et al., 2018). JKNets introduce skip-connection to GNNs: each hidden layer has a direct connection to the output layer, in which the representations are aggregated, e. g., by concatenation. This enables the network to learn from representations corresponding to different levels of the local neighborhood. To isolate the effect of GraphSAINT sampling, we also include JKNets in our comparison.

heading: 4 EXPERIMENTAL APPARATUS

text:
Procedure For each evaluation time step t ∈ [tstart, tend], we construct a subgraph G̃ = (Ṽ , Ẽ) of G induced on Ṽ = {v ∈ V |t− c ≤ tsmin(v) ≤ t} and Ẽ = {(u, v) ∈ E | u, v ∈ Ṽ }. The parameter c denotes the window size, i. e., determines the c time steps that the temporal window spans. Then, we supply the competing models with the subgraph G̃, the corresponding vertex features, and labels for vertices {u ∈ Ṽ | tsmin(u) < t} along with an epoch budget for updating their parameters. The task is to predict the labels for vertices {u ∈ Ṽ | tsmin(u) = t}. Finally, we evaluate the accuracy of the model before incrementing t. We provide an algorithmic view in Appendix A.1.
When advancing from one time step to the next, we consider two options of initializing the model. Using cold restarts corresponds to randomly re-initializing each model in each time step and training it from scratch. In contrast, when using warm restarts, we take the final weights of the previous time step as initialization for the next time step. In both cases, we initialize the additional parameters in the output layer randomly, when new classes appear.
Novel Measure for Distribution of Temporal Differences In the following, we develop a novel dataset-agnostic measure for the distribution of temporal difference within the k-hop neighborhood of each vertex. When k graph convolution layers are used, the features within the k-hop neighborhood of each vertex are taken into account for its prediction. This k-hop neighborhood is referred to as the receptive field of a GNN (Chen et al., 2018). When we incrementally train GNNs on a sliding window through time, the window size determines which vertices are available for training and for inference. Ideally, the temporal window covers all vertices within the GNN’s receptive field, such that GNNs have access to all relevant information.
How many vertices of the receptive field are contained in a temporal window of size c depends on the characteristics of the datasets. Therefore, we introduce a new measure for the distribution of temporal differences tdiffk within the receptive field of a k-layer GNN. Let N k(u) be the k-hop neighborhood of u, i. e., the set of vertices that are reachable from u by traversing at most k edges. Then, we define tdiffk(G) to be the multiset of time differences to past vertices:
tdiffk(G) := {tsmin(u)− tsmin(v)|u ∈ V ∧ v ∈ N k(u) ∧ tsmin(u) ≥ tsmin(v)} (1) Please note that this is a measure to determine comparable window sizes over different datasets and different granularities. It needs to be computed only once per dataseoncet, prior to any training iterations. When we consider a GNN with k graph convolution layers, the distribution tdiffk enumerates the temporal differences within the receptive field of the GNN. In our experiments, we will use the 25th, 50th, and 75th percentiles of this distribution for analyzing the effect of the temporal window size. This choice corresponds to an average receptive field coverage of 25%, 50%, and 75%.
Newly Compiled Datasets Pre-compiled temporal graph datasets for our real-world scenario are surprisingly rare. Therefore we contribute three new temporal graph datasets based on scientific
publications: one temporal co-authorship graph dataset (PharmaBio) as well as two newly compiled temporal citation graph datasets based on DBLP (DBLP-easy and DBLP-hard). These new datasets enable us to simulate a real-world scenario, in which not only new vertices but also new classes (venues) appear over time. Table 1 summarizes the basic characteristics of the datasets and Figure 2 shows the distribution of temporal differences tdiffk for different values of k. For details on the dataset creation procedure as well as degree and label distributions, we refer to Appendix A.2.
Evaluation Measures As our datasets have imbalanced classes, one could argue to use Micro or Macro F1-score as evaluation measure. However, we are primarily interested in the relative performance between limited-window training and training on the full graph. Motivated by realworld scenarios, we chose sample-based F1-score as our evaluation measure (equivalent to accuracy in single-label scenarios). When aggregating results over time, we use the unweighted average.

heading: 5 EXPERIMENTAL RESULTS

text:
We report the results of our experiments along the research questions stated in the introduction.
Q1: Distribution Shift under Static vs Incremental Training In this experiment, we compare a once-trained static model against incrementally trained models. We train the static models for 400 epochs on the data before the first evaluation time step, which comprises 25% of the total vertices. We train incremental models for 200 epochs on temporal windows of 3 time steps (4 on the PharmaBio dataset) before evaluating each time step. All models have comparable capacity.
Figure 3 shows the results. We see that the accuracy of the static models decreases over time on DBLP-easy and DBLP-hard, where new classes appear over time. On PharmaBio, the accuracy of the static models plateaus, while the accuracy of incrementally trained models increases. That confirms our expectations as PharmaBio does not have any new classes, and incrementally trained models merely benefit from the increased amount of training data, while DBLP-easy and DBLPhard do have new classes appearing during the evaluation time frame. In the following experiments, we only use incrementally trained models because they outperform static models in all cases.
Q2: Training with Warm vs Cold Restarts We compare reusing the parameters of the model from the previous time step (warm restart) against randomly re-initializing the model parameters for each temporal window (cold restart). In both cases, we impose a 200 epoch budget per time step. The window size is set to 4 for PharmaBio and 3 for the two DBLP datasets, corresponding to 50% coverage of the GNNs’ receptive field. All models have comparable capacity.
Figure 4 shows the results. We observe that the results obtained by GNNs using warm and cold restarts are close to each other. On DBLP-hard with 23 new classes appearing during the evaluation steps, GS-Mean seems to benefit from warm restarts, while GATs yield better scores when cold restarts are used. On PharmaBio with a fixed class set, both GNNs benefit from reusing parameters from previous iterations. For now, we conclude that both reinitialization strategies are viable and we proceed by running both variants for the next experiments Q3 and Q4.
Q3: Incremental Training on Different Window Sizes We compare the models trained on windows of different sizes and compare it with a model trained on all available data, i. e., the full graph, which is our baseline. We select three window sizes per dataset based on the distribution of temporal differences tdiff2 (see Section 4). These window sized correspond to quartiles, i. e., the windows cover 25%, 50%, and 75% of the GNNs’ receptive field (RF) (see Table 1). Thus, we can compare window sizes across datasets with different characteristics, i. e., connectivity patterns through time and total number of time steps. The epoch budget is 200 and all models have comparable capacity.
Table 2 (top) shows the results. We observe that those GNN variants trained on the full timeline of the graph yield the highest scores on DBLP-easy and DBLP-hard. There, GNNs with window size 1 (25% RF) yield lower scores than training with larger window sizes (50% and 75% RF). On all datasets, the scores for training with limited window sizes larger than 1 are close to the ones of
full-graph training. In summary, window sizes that cover 50% of the receptive field, GNNs and also MLPs achieve at least 95% classification accuracy compared to full-graph training. When 75% of the receptive field is covered by the temporal window, at least 99% accuracy could be retained in all datasets. We refer to Appendix A.4 for extended results including both reinitialization strategies.
Q4: Incremental Training with Scalable GNN Methods Similarly to Q3, we again compare different window sizes against training on the full graph. This time, we focus on using scalable GNN techniques and aim to learn how they perform in conjunction with temporal windows. We further alleviate the fixed-capacity constraint of previous experiments and tune the hidden size as an additional hyperparameter. We refer to Appendix A.3 for details on hyperparameter choices.
We compare Simplified GCN and GraphSAINT, while including JKNet to isolate the effect of GraphSAINT sampling. Table 2 (bottom) shows the results. We observe that, again, limiting the window size to cover 50% of the GNN’s receptive field leads to at least 95% relative accuracy, compared to full graph training. As expected, GraphSAINT sampling (with JKNets as a base model) yields slightly lower scores than full-batch JKNets. On DBLP-hard, simplified GCN outperforms the other, more complex models. In terms of relative performance, limiting the receptive field does not negatively impact GraphSAINT on DBLP-hard and PharmaBio.

heading: 6 DISCUSSION

text:
We have created a new experimental procedure for temporal graphs with new classes appearing over time, for which we contribute three newly compiled datasets with controlled degrees of distribution shift. In this online learning setup, we have evaluated three representative GNN architectures as well as two GNN scaling techniques. With the goal of generalizable results, we have introduced a new measure for the distribution of temporal differences tdiffk, based on which we have selected the temporal window sizes. Our results show that past data can be permanently deleted very early without diminishing the performance of an online vertex classification model. This has direct consequences for online learning of GNNs on temporal graphs and, thus, impacts how GNNs can be employed for numerous real-world applications.
Our main result is that incremental training with limited window sizes is as good as incremental training over the full timeline of the graph (see Q3 and Q4). With window sizes of 3 or 4 (50% receptive field coverage), GNNs achieve at least 95% accuracy compared to using all available data for incremental training. With window sizes of 6 or 8 (75% receptive field coverage), at least 99% accuracy can be retained. This result holds not only for standard GNN architectures but also when scaling techniques such as subgraph sampling are applied on-top of the temporal window. Finally, in almost all experiments, at least 90% of relative accuracy is reached with a window of size 1.
Furthermore, we have verified that incremental training helps to account for distribution shift compared to once-trained, static models (see Q1). We have further investigated on reusing parameters from previous iterations (Q2). Our results show that both strategies are viable, when learning rates are tuned accordingly. During hyperparameter optimization for Q4, in which we alleviated the fixed-capacity constraint, we further noticed that warm restarts are more suitable for higher capacity models with low learning rates, while using cold restarts admits using lower capacity models and higher learning rates (the details of hyperparameter optimization can be found in Appendix A.3).
Even though it was not our main objective to compare the absolute performances of the models, it is noteworthy that simplified GCNs perform surprisingly well on DBLP-hard. Despite the simplicity of the approach, the model yields higher scores than GraphSAINT, JKNets and fixed-capacity GATs, and are only outperformed by GraphSAGE-mean.
A limitation of the present work is that we assume that the true labels of each time step become available as training data for the next time step. In practice, however, only a small fraction of vertices might come with labels for training, while the larger part could be annotated by the model itself. Adapting our experimental procedure to use only a small fraction of true labels in each time step would be an interesting direction of future work.
One could further argue that deleting data that is not linked to the most recent data points would be a viable alternative to deletion based on a fixed time difference. However, this approach would be only feasible in retrospect because, in real-world scenarios, it is impossible to know whether a future data will include a link to a past data point. Still, future work could involve employing other methods to determine what data to delete, such as the personalized PageRank score (Bojchevski et al., 2020).

heading: 7 CONCLUSION

text:
Temporal graphs occur in many real-world scenarios such as citation graphs, transaction graphs, and social graphs. Practitioners face a trade-off between memory requirements, which are tied to the temporal window size, and expected accuracy of their models. Until now, it was not clear, how GNNs can be efficiently trained in those online scenarios, especially when distribution shift becomes an issue. We demonstrate that a high level of accuracy can be retained, when training only on a fraction of the temporal graph, determined by a temporal window. The results of this paper can serve as guidelines for training GNNs on temporal graphs, particularly regarding the intentional forgetting of data while retaining a certain percentage of predictive power. For researchers, we supply our newly compiled datasets along with an implementation of the experimental procedure.
We will make the code and data available to reviewers during the peer-reviewing process as suggested in the ICLR 2021 author’s guide.

heading: A APPENDIX

text:
A.1 ALGORITHM FOR OUR EXPERIMENTAL PROCEDURE
Algorithm 1 outlines our incremental training and evaluation procedure.
Data: Temporal graph G, features X , labels y, time steps t, temporal window size c, epoch budget nepochs
Result: Predicted class labels for vertices in each time step of the graph 1 known classes← ∅; 2 θ ← initialize parameters(); 3 for t? ← tstart to tend do 4 G̃ ← subgraph of G induced on vertices u, where t? − c ≤ tsmin(u) ≤ t? ; 5 ỹtrain ← ỹu, where tsmin(u) < t?; 6 if do cold restart then
// Cold restart: re-initialize all parameters 7 θ ← initialize parameters(); 8 else
// Warm restart: initialize new parameters, copy others 9 tmp← clone(θ);
10 θ ← initialize parameters(); 11 θ|known classes ← tmp|known classes; 12 end 13 θ ← train(θ, G̃, X̃ , ỹtrain) for nepochs epochs; 14 ỹpred ← predict(θ, G̃, X̃) for vertices u, where tsmin(u) = t?; 15 known classes← known classes ∪ set(ỹtrain); 16 end
Algorithm 1: Incremental training procedure of our experimental apparatus
A.2 DATASET DETAILS
In the following, we outline the dataset compilation procedure and supply further descriptive statistics of the resulting datasets.
PharmaBio To compile the PharmaBio dataset, we use the metadata of 543,853 papers by Pharma and Biotech companies from Web of Science (Melnychuk et al., 2019). After removing duplicates, our data cleaning procedure ensures that there is a certain amount of labels for each class per year and that each paper is connected to at least one other paper by a same-author edge. More specifically, we: (1) Keep only papers that are in a journal category with at least 20 papers per year; (2) Keep only papers where at least one of the authors has at least two papers per year; (3) Create vocabulary of words (regular expression: \w\w+) that appear in at least 20 papers globally and keep only papers with at least one of these words. We iterate steps 1–3 until no further paper has been removed in one pass. We end up with 68,068 papers from 23,689 authors working for 68 companies. These papers are distributed across 2,818 journals which are, in turn, categorized into seven journal categories. During preprocessing, each paper becomes a vertex in the graph. The class of the paper is the category of the journal in which it was published. We insert an edge between two vertices, if they share at least one common author (based on string comparison).
DBLP-easy To compile these datasets, we use the DBLP Citation Network dataset (version 10)1 (Tang et al., 2008) as a basis. It comprises 3M citing documents and 25M citations to 2M distinct cited documents, ranging between years. We use venues (conferences or journals) as class labels and use citations as edges. First, we select the subset from 1990 until 2015. Then, we follow a similar procedure as above: (1) Keep only papers from venues that have at least τvenue papers in each year they occur (may be only every second year). (2) Keep only papers that stand in at least
1https://aminer.org/citation
one citation relation to another paper. (3) Remove papers from venues that occur only in a single year. (4) Keep only papers with at least one word from a vocabulary of words that are in at least τwords papers. We iterate steps 1–4 until no further paper has been removed in one pass.
DBLP-hard The difference between DBLP-easy and DBLP-hard is that τvenue := 100 papers in the easy variant and τvenue := 45 papers in the hard variant. The minimum word occurrence threshold τwords is set to 20 for DBLP-easy and 40 for DBLP-hard. Finally, we construct the graph with papers as vertices, citations as edges, and venues as classes.
For all three datasets, we use L2-normalized tf-idf (Salton & Buckley, 1988) representations as vertex features based the corresponding papers’ title. We estimate the power law coefficient α via
maximum likelihood (Newman, 2005) α = 1 + n (∑
u∈V ln degu
degmin
)−1 where degmin is 1 (2 for
PharmaBio).
In Figure 5, we visualize the degree distribution, label distribution, the distribution over years, as well as the distributions of temporal differences (as described in Section 4). All compiled datasets seem to follow a power law distribution, which is typical for citation and co-authorship graphs.
For each dataset, we chose the boundaries for our evaluation time steps [tstart, tend], such that 25% of the total number of vertices lie before tstart, and tend is the final time step. For PharmaBio (1985– 2016), that is tstart = 1999, and for both DBLP variants (1990-2015), that is tstart = 2004. Data before tstart may be used for training, depending on the window size. Regarding changes in the class set (distribution shift), DBLP-easy has 12 venues in total, including one bi-annual conference and four new venues appearing in 2005, 2006, 2007, and 2012. DBLP-hard has 73 venues, including one discontinued, nine bi-annual, six irregular venues, and 23 new venues.
A.3 IMPLEMENTATION DETAILS AND HYPERPARAMETERS
We tune the hyperparameters separately for each window size and each restart configuration. We tune the hyperparameters on DBLP-easy and use the same set of hyperparameters for DBLP-hard and PharmaBio.
For experiments Q1-Q3, we design the models to have a comparable capacity: one hidden layer with 64 hidden units. We use ReLU activation on the hidden layer of MLP and GS-Mean. GS-Mean has one hidden layer, i. e. two graph convolutional layers, with 32 units for self-connections and 32 units for aggregated neighbor representations. GAT has one hidden layer composed of 8 attention heads and 8 hidden units per head, along with one attention head for the output layer. We initialize the model parameters according to Glorot and Bengio (Glorot & Bengio, 2010). For both GS-Mean and GAT, the output of the second layer corresponds to the number of classes. We use dropout probability 0.5 on the hidden units for all models in experiment Q3. We use Adam (Kingma & Ba, 2014) to optimize for cross-entropy. We tune the learning rates on DBLP-easy with a search space of {10−1, 5 ·10−2, 10−2, 5 ·10−3, 10−3, 5 ·10−4, 10−4} and re-use these learning rates for the other datasets. The learning rates are tuned separately for each model, each parameter reinitialization strategy, and each window size. We do not use weight decay because it did not increase the performance (search space {0, 10−3, 5 · 10−4, 10−4, 5 · 10−5, 10−5}). The optimal learning rates can be found in Figure 6 for Q1, Figure 7 for Q2, and Figure 8 for Q3. For implementation of GraphSAGE-mean and GATs, we use DeepGraphLibrary (Wang et al., 2019). All methods are trained transductively: for each new snapshot, the new vertices are inserted into the graph without their labels, then, the models are allowed to (up-)train before making predictions.
For the experiment Q4, we use two hidden layers with 64 hidden units each to make use of jumping knowledge (Xu et al., 2018), as suggested as base architecture in GraphSAINT (Zeng et al., 2020). The learning rate is tuned in the space of {0.0001, 0.001, 0.01, 0.1}. Dropout probability is set to 0.2. We do not use weight decay. We also tune the batch size of GraphSAINT in the range of {256, 512, 2048, 4096}, as subgraph size is an important hyperparameter. For simplified GCN, we tune the learning rate in the range of {0.0005, 0.001, 0.005, 0.01, 0.05} and we set the neighborhood aggregation parameter K to 2, corresponding to two-layer aggregation. For implementation of GraphSAINT and JKNet, we use PyTorch-geometric (Fey & Lenssen, 2019). The optimal hyperparameter values as well as the respective search spaces for experiment Q4 can be found in Figure 3. JKNets and simplified GCNs are trained transductively, while GraphSAINT is trained inductively as suggested by the original work (Zeng et al., 2020).
A.4 EXTENDED RESULTS
Table 4 shows the full results table with both warm and cold restarts for experiment Q3. Table 5 shows the full results table with both warm and cold restarts for experiment Q4. Figure 9 visualizes the results for each time step of experiment Q3.

title: ONLINE LEARNING OF GRAPH NEURAL NETWORKS: WHEN CAN DATA BE PERMANENTLY DELETED?


summaries: This paper proposes a new method for learning representations of images with the goal of improving generalization in RL. The key idea is to regularize the learned feature space by forcing embeddings of states followed by the same action (or sequence of actions) to be more similar than embeddings of states followed by different actions. The method is evaluated on the Procgen and achieves superior performance relative to Rainbow, a standard RL algorithm.

summaries: This paper tackles the problem of representation learning from visualized input. The paper presents "cross-state self-constraint(CSSC)", a technique for regularizing the representation feature space by favoring representation similarity (scalar product between representations) between representations when the agent behaves similarly. The approach is tested with deep RL on the OpenAI ProcGen benchmark.

summaries: The authors modify the Rainbow loss through an additional loss based on a cross-state similarity. The notion of similarity is called in the paper "cross-state self-constraint" - CSSC. The CSSC loss looks very simple and can be applied with other RL algorithms. The loss is defined in terms of an embedding e of the visual input into a 1-dim space. Given three states x_p, x_q, and x_r, their similarity is defined as the scalar product of e(x_p) and e(x_q) minus the scalar product of e(x_q) and e(x_r). It would be useful if the authors include pseudocode how the loss is exactly computed for a given batch of samples. My understanding of the description is that for a given batch the authors generate triples with the same action set and then take as an auxiliary loss the weighted sum of the logarithms of sigmoids of similarities of these triples.

abstractText: Representation learning on visualized input is an important yet challenging task for deep reinforcement learning (RL). The feature space learned from visualized input not only dominates the agent’s generalization ability in new environments but also affect the data efficiency during training. To help the RL agent learn more general and discriminative representation among various states, we present cross-state self-constraint(CSSC), a novel technique that regularizes the representation feature space by comparing representation similarity across different pairs of state. Based on the implicit feedback between state and action from the agent’s experience, this constraint helps reinforce the general feature recognition during the learning process and thus enhance the generalization to unseen environment. We test our proposed method on the OpenAI ProcGen benchmark and see significant improvement on generalization performance across most of Procgen games.

authors:
M.G. Bellemare
Y. Naddaf
J. Veness
M. Bowling

title: The arcade learning environment: An evaluation platform for general agents

venue: Journal of Artificial Intelligence Research,

authors:
Marc G. Bellemare
Will Dabney
Rémi Munos

title: A distributional perspective on reinforcement learning, 2017

authors:
Marc G. Bellemare
Will Dabney
Robert Dadashi
Adrien Ali Taiga
Pablo Samuel Castro
Nicolas Le Roux
Dale Schuurmans
Tor Lattimore
Clare Lyle

title: A geometric perspective on optimal representations for reinforcement learning, 2019

authors:
Karl Cobbe
Oleg Klimov
Chris Hesse
Taehoon Kim
John Schulman

title: Quantifying generalization in reinforcement learning, 2018

authors:
Karl Cobbe
Christopher Hesse
Jacob Hilton
John Schulman

title: Leveraging procedural generation to benchmark reinforcement learning, 2020

authors:
Will Dabney
André Barreto
Mark Rowland
Robert Dadashi
John Quan
Marc G. Bellemare
David Silver

title: The value-improvement path: Towards better representations for reinforcement learning, 2020

authors:
Jesse Farebrother
Marlos C. Machado
Michael Bowling

title: Generalization and regularization in dqn, 2018

authors:
Meire Fortunato
Mohammad Gheshlaghi Azar
Bilal Piot
Jacob Menick
Ian Osband
Alex Graves
Vlad Mnih
Remi Munos
Demis Hassabis
Olivier Pietquin
Charles Blundell
Shane Legg

title: Noisy networks for exploration, 2017

authors:
Matthew Hausknecht
Peter Stone

title: The impact of determinism on learning atari 2600 games. In AAAI Workshop on Learning for General Competency in Video

authors:
Matteo Hessel
Joseph Modayil
Hado van Hasselt
Tom Schaul
Georg Ostrovski
Will Dabney
Dan Horgan
Bilal Piot
Mohammad Azar
David Silver

title: Rainbow: Combining improvements in deep reinforcement learning, 2017

authors:
Max Jaderberg
Volodymyr Mnih
Wojciech Marian Czarnecki
Tom Schaul
Joel Z Leibo
David Silver
Koray Kavukcuoglu

title: Reinforcement learning with unsupervised auxiliary tasks, 2016

authors:
Michael Kearns
Yishay Mansour
Andrew Y. Ng

title: Approximate planning in large pomdps via reusable trajectories

venue: In Proceedings of the 12th International Conference on Neural Information Processing Systems,

authors:
Ilya Kostrikov
Denis Yarats
Rob Fergus

title: Image augmentation is all you need: Regularizing deep reinforcement learning

authors:
Michael Laskin
Kimin Lee
Adam Stooke
Lerrel Pinto
Pieter Abbeel
Aravind Srinivas

title: Reinforcement learning with augmented data, 2020

authors:
Kimin Lee
Kibok Lee
Jinwoo Shin
Honglak Lee

title: Network randomization: A simple technique for generalization in deep reinforcement learning, 2019

authors:
L. Li
T. Walsh
M. Littman

title: Towards a unified theory of state abstraction for mdps

venue: In ISAIM,

authors:
Marlos C. Machado
Marc G. Bellemare
Erik Talvitie
Joel Veness
Matthew Hausknecht
Michael Bowling

title: Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents, 2017

authors:
Andrew Kachites Mccallum
Dana Ballard

title: Reinforcement Learning with Selective Perception and Hidden State

venue: PhD thesis,

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei A Rusu
Joel Veness
Marc G Bellemare
Alex Graves
Martin Riedmiller
Andreas K Fidjeland
Georg Ostrovski
Stig Petersen
Charles Beattie
Amir Sadik
Ioannis Antonoglou
Helen King
Dharshan Kumaran
Daan Wierstra
Shane Legg
Demis Hassabis

title: Human-level control through deep reinforcement learning

authors:
Steffen Rendle
Christoph Freudenthaler
Zeno Gantner
Lars Schmidt-Thieme

title: Bpr: Bayesian personalized ranking from implicit feedback

authors:
John Schulman
Filip Wolski
Prafulla Dhariwal
Alec Radford
Oleg Klimov

title: Proximal policy optimization algorithms, 2017

authors:
David Silver
Julian Schrittwieser
Karen Simonyan
Ioannis Antonoglou
Aja Huang
Arthur Guez
Thomas Hubert
Lucas Baker
Matthew Lai
Adrian Bolton
Yutian Chen
Timothy Lillicrap
Fan Hui
Laurent Sifre
George van den Driessche
Thore Graepel
Demis Hassabis

title: Mastering the game of go without human knowledge

venue: Nature,

authors:
Xingyou Song
Yiding Jiang
Stephen Tu
Yilun Du
Behnam Neyshabur

title: Observational overfitting in reinforcement learning, 2019

authors:
Aravind Srinivas
Michael Laskin
Pieter Abbeel

title: Curl: Contrastive unsupervised representations for reinforcement learning, 2020

authors:
Yuval Tassa
Yotam Doron
Alistair Muldal
Tom Erez
Yazhe Li
Diego de Las Casas
David Budden
Abbas Abdolmaleki
Josh Merel
Andrew Lefrancq
Timothy Lillicrap
Martin Riedmiller

title: Deepmind control suite, 2018

authors:
Hado van Hasselt
Arthur Guez
David Silver

title: Deep reinforcement learning with double qlearning

authors:
Ziyu Wang
Tom Schaul
Matteo Hessel
Hado van Hasselt
Marc Lanctot
Nando de Freitas

title: Dueling network architectures for deep reinforcement

authors:
Chiyuan Zhang
Oriol Vinyals
Remi Munos
Samy Bengio

title: A study on overfitting in deep reinforcement learning, 2018

heading: 1 INTRODUCTION

text:
Deep Reinforcement learning has achieved tremendous success on mastering video games(Mnih et al., 2015) and the game of GO(Silver et al., 2017). While training agent by using deep reinforcement learning algorithms, we usually assume that the agent could extract appropriate and effective features from different states and take actions accordingly. However, as more and more research works(Zhang et al. (2018), Song et al. (2019), Dabney et al. (2020)) have pointed out, even welltrained RL agents that learns from visualized input tend to memorizing spurious pattern rather than understanding the essential generic features of a given state. For example, an agent might pay more attention to the change of irrelevant background rather than noticing the obstacles or enemies(Song et al., 2019).
To improve generalization in the new environment, various kinds of regularization method like dropout(Farebrother et al., 2018) and data augmentation(Laskin et al., 2020) has been proposed and tested in combination with reinforcement learning. Conventional methods like dropout and batch-norm has been proven to be effective in supervised-learning, and for self-supervised learning like RL we see multiple related applications across various environments. Data augmentation like random crop(Laskin et al., 2020) or random convolution(Lee et al., 2019) have also been proposed recently and provide considerable generalization enhancement to the unseen levels of various tested environment(Tassa et al. (2018), Cobbe et al. (2018), Cobbe et al. (2020)). The agent is acting on multiple augmented views of the same input and learn from these prior injected data. However, modifying state information(injecting prior to the data) may be risky or even detrimental for representation learning because vital features may be altered or lost (ex: flipping state image might change the corresponding behavioral meaning, cropping the input image might lose critical features like the enemy position in the game).
To avoid losing informative features of the visualized input, we choose a different approach. As a human learner, we rarely depend on multiple augmented views of the same input to discriminate important or fictitious features. Instead, human learners try to recognize general patterns across multiple states and act accordingly. In other words, if the same action(or behavior) has been conducted by a well-trained agent in two different states, we would infer that the agent has conceived similar feature patterns in these states. For example, if one car stops for ninety seconds at two different intersections, we would guess that the car might be stopped by the red light at both places(Figure 1b).
From here we get the intuition about the relation between action(or behavior) and representation feature space learned by the agent: for a RL agent acting rationally across sequence of states, its behavior would be similar if it perceives similar critical patterns while acting differently if it perceives different patterns. Based on this intuition, we designed a novel constraint that performs regularization directly in the representation feature space of the learning agent. Our hypothesis for this constraint is simple: states in which the rational agent behaves identically should share more representation resemblance than states the agent behave differently.
We test this novel constraint in combination with Rainbow(Hessel et al., 2017), the state-of-theart Q-learning method that combines numerous improvements with the original DQN model(Mnih et al., 2015). Inspired by the pair-wise structure used in BPR-opt(Rendle et al., 2012), we design the self-constraint based on the agent’s behavior and utilize implicit feedback between positive and negative state pairs in the replay buffer. One thing worth noticing is that no change is needed for the underlying RL algorithm or model to adapt the proposed method, and it can be easily applied to other models with minimal effort(Figure 1a).
To measure the improvement on generalization to unseen environment levels, We test CSSC across 16 games on the OpenAI ProcGen benchmark(Cobbe et al., 2020). We see significant improvement on generalization capability for most ProcGen games in comparison with base Rainbow model.
We highlight the main contributions of CSSC as follows:
• Directly optimize feature generalization across various input states • Requires no additional modification on the input data and the base model • Enhance generalization and data efficiency on existing RL methods

heading: 2 RELATED WORK

heading: 2.1 AUXILIARY TASK FOR REPRESENTATION LEARNING IN RL

text: Representation Learning has been a vital part for deep RL algorithms. Even though the main goal of RL is to find the optimal value function, Mccallum & Ballard (1996) and Li et al. (2006) show that a representation specialized to this function may not be suitable for the sequence of value functions leading to it. On the other hand, Dabney et al. (2020) argue that the path toward optimal value function might be hindered by overfitting the representation to any intermediate value function during training. One popular and effective method to address this challenge is by using auxiliary tasks(Jaderberg et al. (2016), Bellemare et al. (2019)). Dabney et al. (2020) also propose new auxiliary tasks by considering the value-improvement path holistically.

heading: 2.2 REGULARIZATION ON RL

heading: 2.2.1 ADDING STOCHASTICITY TO RL

text:
Conventional practices like stochastic policy(Hausknecht & Stone, 2015), random starts(Mnih et al., 2015), sticky actions(Hausknecht & Stone, 2015) and frame skipping are wildly used for popular
tasks like Atari(Machado et al., 2017). By adding stochasticity to the environments during training and testing, we would prevent simple algorithms like trajectory tree(Kearns et al., 1999) and brute(Machado et al., 2017) from optimizing over open-loop sequences of actions without even considering the input states. However, as Zhang et al. (2018) has pointed out, injecting stochasticity to the maze-like environments does not necessarily prevent the deep RL agents from overfitting.

heading: 2.2.2 CONVENTIONAL REGULATIZATION ON RL

text: For deep supervised learning, regularizations has long been a major issue as generalization from training to test set is the major concern. Common regularization practices like L2 regularization, dropout, batch-normalization from supervised learning has also been tested in the reinforcement learning scenario. Cobbe et al. (2018) and Farebrother et al. (2018) show that dropout and L2 regularization improve generalization to test environments in Coinrun(Cobbe et al., 2018) and Atari 2600(Bellemare et al., 2013) respectively.

heading: 2.2.3 DATA AUGMENTATION ON RL

text: For supervised learning related to images or computer vision, data augmentation is a popular way to enhance performance by injecting useful priors on the training data. In recent years, we see numerous data augmentation methods for RL that improve generalization or data efficiency. Lee et al. (2019) introduce a randomized convolution network that randomly perturbs input features. Srinivas et al. (2020) utilize contrastive learning and show considerable performance gains in terms of sample-efficiency. Kostrikov et al. (2020) uses augmented data and weighted Q-functions to achieve state-of-the-art data-efficiency on the DMControl(Tassa et al., 2018). Laskin et al. (2020) investigate ten different data augmentation on RL and point out that random crop is the most effective on DMControl(Tassa et al., 2018)

heading: 3 BACKGROUND

text: CSSC is a general framework of cross-state representation regularization for RL. In principle, one can apply CSSC to other variation of DQN or policy-based models for discrete action-space environments. In this work we pick Rainbow (Hessel et al., 2017) and PPO (Schulman et al., 2017) as our base model to show that CSSC is compatible with the original Nature DQN(Mnih et al., 2015), its multiple improvements and policy-based algorithms. In the following subsections we will review Rainbow DQN and introduce the concept of implicit feedback in Bayesian Personalized Ranking (BPR) proposed by Rendle et al. (2012).

heading: 3.1 RAINBOW

text:
In combination with a convolutional neural network as visualized input encoder, Deep Q network(Mnih et al., 2015) demonstrates that it is possible to use neural network as a function approximator that maps raw pixels to Q values. Since then, multiple improvements such as Double Q Learning(van Hasselt et al., 2015), Dueling Network Architecture(Wang et al., 2015), Prioritized Experience Replay(Schaul et al., 2015) and Noisy Networks(Fortunato et al., 2017) have been proposed. In addition, Bellemare et al. (2017) proposed the method of predicting a distribution over possible value support through the C51 algorithm. By combining all the above techniques into a single off-policy algorithm, Rainbow DQN showcases the state-of-the-art sample-efficiency on Atari Benchmarks. The resulting loss function for Rainbow DQN is as follows:
LRainbow = DKL(Φzd(n)t ||dt) (1)
where Φz is the projection onto fixed support z. d (n) t and dt are the n-step target return distribution and the model-predicted return distribution respectively.

heading: 3.2 BPR-OPT

text:
As opposed to explicit feedback like user ratings, implicit feedback in recommendation systems focuses on interactions like click or view between users and items. In implicit feedback system only
positive observations are available, and non-observed user-item pairs -e.g. a user has not view an item yet - are considered as negative observations. Instead of rating prediction, BPR-opt(Rendle et al., 2012) is designed for direct ranking optimization based on the implicit feedback between users and items. BPR extends the user preference from observed interaction pairs to non-observed data by ranking the preference of positive observation and negatived observation across the training data. The formulation of the maximum posterior estimator for the personalized ranking optimization (BPR-opt) can be written as follows:
ln p(Θ| >u) = ∑
(u,i,j)∈Ds
lnσ(x̂uij)− λΘ||Θ||2 (2)
where Θ represents the parameter vector of the base model. Ds represent the batch samples from training data. p(Θ| >u) is the posterior probability conditioned on latent preference structure >u for user u, λΘ is the model specific regularization parameter, σ is the sigmoid function, and x̂uij(Θ) is the real-valued function model Θ which captures the preference relationship between user u, item i and item j. Rendle et al. (2012) use x̂uij := x̂ui − x̂uj to indicate that the user u prefers item i over item j.

heading: 4 METHOD

text: The main idea of CSSC is to extend the similarity ranking across various state representation based on our hypothesis: representations motivating identical behavior should share more similarity than those motivating different behavior. We name this method as ”self-constraint” to emphasize that the state pairing is decided by the agent’s behavior rather than pre-defined fixed labels. In the following subsection below, we introduce the following concepts to provide further explanation and insight: (i) definition of the behavior of an agent at a given state (ii) implicit feedback between state and behavior (iii) cross-state self-constraint as an auxiliary loss for representation regularization

heading: 4.1 BEHAVIOR DEFINITION

text: We describe a typical Markov Decision Process(MDP) as (X , A, R, P, γ) with state space as X , action space as A, reward function as R, state transition function as P and discount factor as γ. The agent would take an action ai at state xi and then being transited to xi+1 by the environment with a given step reward ri. Here we define the behavior set Bni = {(ai, ai+1, ..., ai+n−1)|a ∈ A} as a set of action series of length n taken by the agent since state xi. For bni ∈ Bni and bnj ∈ Bnj , bni = b n j only if ai+p = aj+p for 0 ≤ p ≤ n − 1. With this definition in mind, we can infer that if the agent conduct the behavior b2i = (left, fire) at state xi, it would move left in state xi and fire in the next state xi+1. In the following paragraph we coin names like unigram, bigram and trigram for behaviors of length one, two and three respectively.

heading: 4.2 IMPLICIT FEEDBACK IN REINFORCEMENT LEARNING

text: In the traditional deep Q-learning scenario, each state representation is highly correlated to neighboring states by the Bellman equation during the training process. However, observational overfitting could still happen as long as the representation of neighboring states can fit to specific sub-optimal version of Q-function indefinitely as mentioned in Dabney et al. (2020). Besides the base RL algorithm, we can view the interaction between state and behavior as an implicit feedback system by regarding states sharing same action as positive observation. The general feature among these positive observation would be reinforced if we compare their similarity with negative observation -e.g. states sharing different action. Through this “ranking” procedure the pair-wise relationship would be extended across non-neighboring states and therefore preventing observational overfitting to specific Q-function.

heading: 4.3 IMPLEMENTATION OF CROSS-STATE SELF-CONSTRAINT IN COMBINATION WITH RAINBOW AND PPO

text:
For each sample of state triples(xp, xq, xr) ∈ X with (bnp , bnq , bnr ) ∈ Bn and bnp = bnq 6= bnr , we decompose the estimator x̂pqr and define it as:
x̂pqr := x̂pq − x̂pr = eθ(xp) · eθ(xq)− eθ(xp) · eθ(xr) (3)
where eθ is the encoder function with weight θ that maps the pixel input to 1-D array feature vector with shape like [element 0, element 1, ..., element n] as the state representation. We directly perform inner-product on eθ(xp) and eθ(xq) to calculate the representation similarity x̂pq between xp and xq . Please note that the encoder function is the same part of the original base model used for feature extraction on visualized input. For more details about neural network structures used in this paper, please refer to Figure 7 and Figure 8. To sample these state triplets without modifying the base DQN or PPO algorithm, we collect these state triples in the same batch of transitions used to calculate Bellman loss or policy loss. For policy-based algorithms and DQN without prioritized replay (Schaul et al., 2015), we pair up the state triples for each transition in the sample and calculate the CSSC loss as follows:
LCSSC = − 1
NDs ∑ (p,q,r)∈Ds lnσ(x̂pqr) (4)
where Ds represents the sample batch of size NDs from the replay buffer and σ is the sigmoid function. Then, we train the base algorithm in combination with the auxiliary CSSC loss as follows:
Ltotal = Lbase + βcssc · LCSSC (5)
where βcssc is the hyperparameter to control the contribution of CSSC during training. For pseudocode of PPO with unigram CSSC, please refer to Algorithm 2 in the appendix.
In the case of Rainbow with CSSC, we design the loss function in combination with the importance sampling (IP) weight as follows:
L̂total = ( ̂LRainbow ⊕ (βcssc · L̂CSSC)) ŴIP (6)
where ⊕
and are element-wise add and multiplication respectively. For pseudocode of Rainbow with unigram CSSC, please refer to Algorithm 1 in the appendix.
We find that setting βcssc to 0.01 works quite well in most cases, so we stick with this setting for all the experiment conducted in the next section.

heading: 5 EXPERIMENT

text: Our primary goal for CSSC is to enhance the generalization capability of RL algorithm to unseen levels that share similar mechanism. Fortunately, OpenAI ProcGen(Cobbe et al., 2020) presents a collection of game-like environments where the training and testing environments differs in visual appearance and structure. Therefore, we evaluate CSSC in three different ways:(i) generalization improvement on 12 easy-mode games and 8 hard-mode games with Rainbow on OpenAI ProcGen (ii) generalization improvement on 16 easy-mode games with PPO on OpenAI ProcGen (iii) performance improvement on 32 games with Rainbow on Gym Atari (iv) visualization on the representation space learned with CSSC.

heading: 5.1 ENVIRONMENT AND MODEL SETTING

text: For the following experiments, we use the IMPALA CNN architecture recommended by Cobbe et al. (2020) for the Rainbow and PPO model on ProcGen benchmark. For the Gym Atari benchmark, we stay with the Nature CNN as mentioned in Hessel et al. (2017) for the Rainbow model. All the experiments in this paper are conducted in the single-agent setting. For all hyperparameter used on ProcGen and Atari benchmark, please refer to Table 3 in the Appendix. We use “unigram CSSC” or “bigram CSSC” to indicate the behavior length used to pair up the state triples for CSSC.

heading: 5.2 GENERALIZATION ON PROCGEN IN EASY MODE WITH RAINBOW

text:
As Cobbe et al. (2020) have suggested, we conduct the training of 25 million timesteps on 200 training levels and evaluate the generalization improvement on the full distribution of testing levels across 12 ProcGen games. We test both the unigram and bigram CSSC in comparison with vanilla Rainbow and see significant improvement on testing performance. To evaluate the mean normalized score for bigram and unigram CSSC across 12 games, we follow the normalization method used in Cobbe et al. (2020) and show the result in Figure 2a and Figure 12a respectively. We also display the learning curve of bigram-CSSC in Figure 3 and unigram-CSSC in Figure 13. In the following we summarize the main findings below:
• In supervised learning, posing regularization or constraint to the model would usually improve its testing performance on unseen data at the expense of hurting training performance. However, we see that the proposed self-constraint improves both training and testing performance across most of the 12 game tested.
• For games like Starpilot, Chaser and Bigfish, we see that the testing performance is even better than the training performance of vanilla Rainbow.
• For the mean normalized score in Table 1, Bigram-CSSC and Unigram-CSSC bring 85% and 64% improvement respectively on the testing performance in comparison with base Rainbow model.

heading: 5.3 GENERALIZATION ON PROCGEN IN HARD MODE WITH RAINBOW

text:
To further explore the generalization capability in more complicated and challenging tasks, we examine the generalization improvement brought by CSSC on 8 ProcGen games.We use 500 training levels for 30 million timesteps of training across 3 seeds and evaluate generalization on the full distribution of testing levels. We test the bigram CSSC in comparison with the normal version of Rainbow across three different seeds and see significant improvement on testing performance. The learning curve of bigram CSSC is summarized in Figure 4. To evaluate the mean normalized score for bigram CSSC across 8 games in hard mode, we also follow the normalization method used in
Cobbe et al. (2020) and show the result in Figure 2b. In the following we summarize the main findings below:
• As shown in Figure4, CSSC substantially improves both training and testing performance in Bigfish, Dodgeball, Starpilot, Fruitbot and Bossfight.
• In particular, we see nearly 4x performance jump in Bigfish at 30M timestep in comparison with the base Rainbow model. The mean episodic return at 30M timestep of bigram CSSC is even higher than that of PPO at 200M timestep as shown in Figure 4 of Cobbe et al. (2020).
• In the case of Heist (a puzzle-solving task in maze-like layout), coinrun(a 2-D scroll platform game) and Plunder(a challenging shooting game), the gain from CSSC is not as obvious because all these games require careful manipulation and planning. Add constraint that modifies state representation directly would be risky or even detrimental for the learning process of the base RL algorithm.

heading: 5.4 GENERALIZATION ON PROCGEN IN EASY MODE WITH PPO

text: We test the CSSC with PPO on all the 16 games of the Procgen benchmark in Easy mode. We conduct the training of 25 million timesteps across 3 seeds on 200 training levels and evaluate the generalization improvement on the full distribution of testing levels across all 16 ProcGen games. From the normalized learning curve shown in Figure 5a we can tell that CSSC helps reduce the gap between training and testing performance. For detailed final scores and learning curves, please refer to Table 7 and Figure 14, 15 in the Appendix.

heading: 5.5 PERFORMANCE ON GYM ATARI WITH RAINBOW

text: We take Gym Atari benchmark (Brockman et al., 2016) as our second set of environments to measure the effectiveness of CSSC. Even though this classic benchmark does not explicitly split the training levels out of the training levels in all environments, we still see significant improvement on 23 out of 38 games tested as shown in Figure 5b. For training hyperparameters and scoreboard on Gym Atari benchmark, please refer to Table 3 and 8 in the Appendix.

heading: 5.6 VISUALIZATION OF REPRESENTATION EMBEDDING

text: To give a more tangible explanation about the effectiveness of CSSC, we plot the representation distribution in the embedding feature space across 4096 states from the replay buffer. We first perform dimension reduction on these state embeddings using principal decomposition analysis and label each embedding point with the index of corresponding action. Here we show the embedding space of both Rainbow and bigram-CSSC models trained to play the Bigfish game. In figure 6 we can see that states of the same action are more clustered in bigram-CSSC than that of the vanilla Rainbow model. We believe this is the possible reason behind the significant improvement on generalization as shown in Figure 4. For representation visualization in other ProcGen games, please refer to A.4.

heading: 6 CONCLUSION

text: In this paper we propose a novel regularization on state representation learning based on the connection between agent behavior and the visual input. Our hypothesis is derived from the observation that the behavior of a rational agent would have certain relationship with general cross-state features or patterns. We see significant improvement on generalization brought by the proposed cross-state self-constraint(CSSC) on most of the games in OpenAI ProcGen benchmark. The connection between behavior and conceived visual input can be considered as some kind of “motivation” that acts as a decisive factor behind the learned policy. It worth further study to better understand the derivation and transformation of agent’s ”motivation” during the Markov Decision Process, and we believe the concept proposed in this work would facilitate more research in this direction.

heading: A APPENDIX

text:
A.1 NEURAL NETWORK ARCHITECTURE
A.2 HYPERPARAMTERS AND MODEL SETTING FOR OPENAI PROCGEN AND GYM ATARI BENCHMARK
A.3 SCOREBOARDS ON OPENAI PROCGEN
A.4 VISUALIZATION OF REPRESENTATION EMBEDDING ON OPENAI PROCGEN GAMES
A.5 GENERALIZATION ON PROCGEN IN EASY MODE FOR RAINBOW UNIGRAM-CSSC
A.6 GENERALIZATION ON PROCGEN IN EASY MODE FOR PPO WITH CSSC
A.7 PSEUDOCODE FOR CSSC EXPERIMENT
A.8 EVALUATION OF BIGRAM CSSC WITH RAINBOW ON GYM ATARI BENCHMARK
Algorithm 1 Rainbow + CSSC (unigram) 1: Input: minibatch size k, multi-step return n, replay period K and buffer size N , exponents α
and β, gamma γ, CSSC coefficient βcssc, total-timesteps T . 2: Initialize replay memoryH = Ø, feature extractor θ, return distribution predictor Θ, p1 = 1 3: Observe state s0 and choose action a0 ∼ πθ(s0) 4: for t = 1 to T do 5: Observe state st, reward r (n) t , done flag dt, new state st+n 6: Store transition jt = (st, at, r (n) t , dt, st+n) inH with maximal priority pt = maxi<t pi 7: if t mod K ≡ 0 then 8: Sample batch of transition J = [j0, j1, ..., jk|j ∼ P (j) = pαj /Σipαi ] 9: Compute importance-sampling weight: Ŵ = [w0, w1, ..., wk|wj = (N · P (j))−β/maxi wi] 10: Predict state feature vector eθ(sj), eθ(sj+n) and return distribution dj , d (n) j =
Θ(eθ(sj)),Θ(eθ(sj+n)) for each transition in the batch 11: Compute ̂LRainbow = [l0, l1, ..., lk|lj = DKL(Φzd(n)j ||dj)] using distribution projec-
tion function Φz 12: Update transition priority pj ← lj for each transition in the batch 13: Sample positive pair (sp, sq), p 6= q with jp, jq ∈ J and behavior b1p = b1q for each
transition jp in J 14: Sample negative pair (sp, sr), p 6= r with jp, jr ∈ J and behavior b1p 6= b1r for each
transition jp in J 15: Compute L̂CSSC = [ŝ0p0q0r0 , ..., ŝkpkqkrk |ŝjpjqjrj := −1.0 × σ(eθ(spj ) · eθ(sqj ) −
eθ(spj ) · eθ(srj ))] 16: Compute L̂total = ( ̂LRainbow ⊕ (βCSSC · L̂CSSC)) Ŵ where ⊕ and are element-
wise add and multiplication respectively 17: Fit Θ and θ with Adam optimizer to minimize L̂total.mean() 18: end if 19: end for
Algorithm 2 PPO + CSSC (unigram) 1: Input: minibatch size k, CSSC coefficient βcssc, total-timesteps T , clip range 2: Initialize rollout buffer H = Ø, feature extractor θ, policy parameters Θ, value function param-
eters φ 3: for t = 0 to T do 4: Collect set of trajectories Dk = {Ti} by running policy πk = π(θk) in the environment 5: Compute advantages estimates Ât using current value function Vφ 6: Store transition jt = (st, at, rt, dt, Ât, log(π(θk))) inH 7: if rollout bufferH is full then 8: for each batch inH do 9: Predict state feature vector eθ(sj), log prob, values using πθ and Vφ for transitions
in the batch 10: Compute ratio = exp(log prob - batch.old log prob) 11: Compute policy loss = batch.advantages · clamp(ratio, 1 - clip range, 1 + clip range) 12: Compute Lpolicy = policy loss.mean() 13: Sample positive pair (sp, sq), p 6= q with jp, jq ∈ J and behavior b1p = b1q for each
transition jp in batch transitions J 14: Sample negative pair (sp, sr), p 6= r with jp, jr ∈ J and behavior b1p 6= b1r for each
transition jp in batch transitions J 15: Compute cssc loss = [ŝ0p0q0r0 , ..., ŝkpkqkrk |ŝjpjqjrj := −1.0×σ(eθ(spj )·eθ(sqj )−
eθ(spj ) · eθ(srj ))] 16: Compute LCSSC = cssc loss.mean() 17: Fit Θ, θ and φwith Adam optimizer to minimize Ltotal = LRainbow+βcssc ·LCSSC 18: end for 19: end if 20: end for

title: CROSS-STATE SELF-CONSTRAINT FOR FEATURE GEN- ERALIZATION IN DEEP REINFORCEMENT LEARNING