Inductive representation learning on temporal graphs
Authors: da Xu
chuanwei ruan
evren korpeoglu
sushant kumar
kannan achan
Venue:  (2020)
Keywords: temporal graph
inductive representation learning
functional time encoding
self-attention

Abstract: Inductive representation learning on temporal graphs is an important step toward salable machine learning on real-world dynamic networks. The evolving nature of temporal dynamic graphs requires handling new nodes as well as capturing temporal patterns. The node embeddings, which are now functions of time, should represent both the static node features and the evolving topological structures. Moreover, node and topological features can be temporal as well, whose patterns the node embeddings should also capture. We propose the temporal graph attention (TGAT) layer to efficiently aggregate temporal-topological neighborhood features to learn the time-feature interactions. For TGAT, we use the self-attention mechanism as building block and develop a novel functional time encoding technique based on the classical Bochner's theorem from harmonic analysis. By stacking TGAT layers, the network recognizes the node embeddings as functions of time and is able to inductively infer embeddings for both new and observed nodes as the graph evolves. The proposed approach handles both node classification and link prediction task, and can be naturally extended to include the temporal edge features. We evaluate our method with transductive and inductive tasks under temporal settings with two benchmark and one industrial dataset. Our TGAT model compares favorably to state-of-the-art baselines as well as the previous temporal graph embedding approaches.

Published as a conference paper at ICLR 2020
INDUCTIVE REPRESENTATION LEARNING ON TEMPORAL GRAPHS
Da Xu', Chuanwei Ruan", Evren Korpeoglu, Sushant Kumar, Kannan Achan Walmart Labs Sunnyvale, CA 94086, USA (Da. [u, Chuanwei Ruan, EKorpeoglu, 3Xumar4, KAchan (rrchan]@wali @wa aeaalmmrre ma tt labslab.... com com
ABSTRACT
Inductive representation learning on temporal graphs is an important step toward salable machine learning on real-world dynamic networks. The evolving nature of temporal dynamic graphs requires handling new nodes well as capturing tem- poral patterns. The node embeddings, which are now functions of time, should represent both the static node features and the evolving topological structures. Moreover, node and topological features can be temporal as well, whose patterns the node embeddings should also capture. We propose the temporal graph at- tention (TGAT) layer to efficiently aggregate features well as learn the time-feature interactions. For TGAT, use the self-attention mechanism as building block and develop a novel functional time encoding technique based on the classical Bochner's theorem from harmonic anal- ysis. By stacking TGAT layers, the network recognizes the node embeddings as functions of time and is able inductively infer embeddings for both new and observed nodes as the graph evolves. The proposed approach handles both node classification and link prediction task, and can be naturally extended to include the temporal edge features. We evaluate our method with transductive and induc- tive tasks under temporal settings with two benchmark and one industrial dataset. Our TGAT model compares favorably to state-of- baselines as well as the previous temporal graph embedding approaches.
neighborhood
INTRODUCTION
The technique of learning lower-dimenssonal vector embeddings on graphs have been widely ap- plied to graph analysis tasks (Perozzi et al. [0144] Tang et al., 2015 Wang et al. (2016) and deployed in industrial systems (Ying et al. [0118] Wang et al. 2a). Most of the graph representation learning approaches only accept static or non-temporal graphs as input, despite the fact that many graph-stree graph-structured data are dependent... In social network, citation network, question answering forum and user-item interaction system, graphs are created as temporal interactions between nodes. Using the final state as a static portrait of the graph is reasonable some cases, such as the protein- protein interaction network, as long as node interactions are timeless in nature. Otherwise, ignoring the temporal information can severely diminish the modelling efforts and even causing questionable inference. For instance, models may mistakenly utilize future information for predicting past inter- actions during training and testing if the temporal constraints are disregarded. More importantly, the dynamic and evolving nature of many graph-related problems demand explicitly modelling of the timeliness whenever nodes and edges are added, deleted or changed over time.
Learning representations temporal graphs is extremely challenging, and it is not until recently that several solutions are proposed (Nguyen et al. 2018 Li al. 2018 Goyal et al.) 2018 Trivedi et al.) 2018). We conclude the challenges in three folds. Firstly, model the temporal dynamics, node embeddings should not be only the projections of topological structures and node features but also functions of the continuous time. Therefore, in addition the usual vector space, temporal representation learning should be operated in some functional space as well. Secondly, graph topo- logical structures are no longer static since the nodes and edges are evolving over time, which poses
Both authors contributed equally this research.

---

Published as a conference paper at ICLR 2020
(A)
(B)
(C)
11
17
Projected 2-3
8)
(8, Q)
Time
+AA C)
(A.8)
+(0.A)
(0.0C)
Figure Visual illustration for several complications from the temporal graphs. (A). The gen- eration process of temporal graph and its snapshots. It is obvious that the static graphs in the snapshots only reflect partial temporal information. (B). The final state of the temporal graph when projected to the time-independent 2-D plane. Other than the missing temporal information, the multi-edge situation arises as well. (C). When predicting the link between node A and C at time 13. the pressage-passingg paths should be subject temporal contraints. The solid lines give the appropriate directions, and the dashed lines violates the temporal constraints.
temporal constraints neighborhood aggregation methods. Thirdly, node features and topolog- ical structures can exhibit temporal patterns. For example, node interactions that took place long ago may have less impact on the current topological structure and thus the node embeddings. Also, some nodes may possess features that allows them having more regular or recurrent interactions with others. We provide sketched plots for visual illustration in Figure
Similar to its non-temporal counterparts, in the real-world applications, models for representa- tion learning temporal graphs should be able quickly generate embeddings whenever quired, in an inductive fashion. GraphSAGE (Hamilton et af.) 2017a) and graph attention network (GAT) (Veličković et al. (217)) capable of inductively generating embeddings for unseen nodes based on their features, however, they do not consider the temporal factors. Most of the temporal graph embedding methods can only handle transductive tasks, since they require re-training or the gradient calculations to infer embeddings for unseen nodes or node em- beddings for a new timepoint. In this work, we aim developing an architecture to inductively learn representations for temporal graphs such that the time-aware embeddings (for unseen and observed nodes) can be obtained via single network forward pass. The key to our approach is the combi- nation of the self-attention mechanism (Vaswani et al. 2017) and novel functional time encoding technique derived from the Bochner's theorem from classical harmonic analysis (Loomis) 2013).
The motivation for adapting self-attention to inductive representation learning temporal graphs is to identify and capture relevant pieces of the temporal neighborhood information. Both graph con- volutional network (GCN) (Kipf & Welling, 2016a) and GAT implicitly explicitly assigning different weights to neighboring nodes /Veličković et al. 2017) when aggregating node features. The self-attention mechanism initially designed to recognize the relevant parts of input sequence in natural language processing. As a discrete-event sequence learning method, self-attention outputs a vector representation of the input sequence weighted sum of individual entry embeddings. Self- attention enjoys several advantages such as parallelized computation and interpretability (Vaswani al. 2017). Since it captures sequential information only through the positional encoding, tem- poral features can not be handled. Therefore, we are motivated to replace positional encoding with some vector representation of time. Since time is continuous variable, the mapping from the time domain to vector space has to be functional. We gain insights from harmonic analysis and propose a theoretical-grounde functional time encoding approach that is compatible with the self-attention mechanism. The temporal signals then modelled by the interactions between the functional time encoding and nodes features as well as the graph topological structures.
To evaluate our approach, we consider future link prediction on the observed nodes transductive learning task, and on the unseen nodes as inductive learning task. We also examine the dynamic node classification task using node embeddings (temporal versus non-temporal) features to demonstrate the usefulness of our functional time encoding. We carry out extensive ablation studies and sensi- tivity analysis show the effectiveness of the proposed functional time encoding and TGAT- -lyer.
2

---

Published as a conference paper at ICLR 2020
2 RELATED WORK
Graph representation learning. Spectral graph embedding models operate on the graph spectral domain by approximating, projecting expanding the graph Laplacian (Kipf & Welling 2016a Henaff et al. 2015| Defferrard et al. 2016). Since their training and inference are conditioned on the specific graph spectrum, they not directly extendable to temporal graphs. Non-spectral ap- proaches, such as GAT, GraphSAGE and MoNET, (Monti et al. 2017) rely on the localized neigh- bourhood aggregations and thus not restricted to the training graph. GraphSAGE and GAT also have the flexibility to handle evolving graphs inductively. To extend classical graph representation learning approaches the temporal domain, several attempts have been done by cropping the tem- poral graph into a sequence of graph snapshots (Li et al. 2018 8 Goyal et al. 2018 Rahman et al., 2018 Xu al. 2019b), and some others work with temporalyy persistent node (edges) (Trivedi et al, 2018 Ma et al. (018))_ Nguyen et al. (2018) proposes a node embedding method based on temporal random walk and reported state-of-the-arr performances. However, their approach only generates embeddings for the final state of temporal graph and can not directly apply to the inductive setting,
Self-attention mechanism. Self-attention mechanisms often have two components: the embedding layer and the attention layer. The embedding layer takes an ordered entity sequence input. Self- attention uses the positional encoding, i.c. each position is equipped with a vector p (fixed or learnt) which is shared for all sequences. For the entity sequence e (e1, ((1,-..;(i) ei), the embedding layer takes the sum or concatenation of entity embeddings (or features) (z E Rd) and their positional encodings input:
Ze Z PI.....Z.. Ze, + p.]' T E Ridd or -. - [
[P:]" E Rix(++))) (1)
where || denotes concatenation operation and dnes is the dimension for positional encoding. Self- attention layers can be constructed using the scaled dot-product attention, which defined as:
QKT
Attn( (Q, V) ssotmmxx
vd
where Q denotes the 'queries', K the 'keys' and V the 'values'. In Vaswani et al. (2017), they are treated as projections of the output Ze: Q = Zo Wo, K = Ze W.. K. V Zo W where Wo. W R and Wy y are the projection matrices. Since each row of Q, K and represents an entity, the dot- not-product attention takes a weighted sum of the entity 'values' in V where the weights are given by the interactions of entity 'query-key' pairs. The hidden representation for the entity sequence under the dot-product attention is then given by lte = Attn( Q K, V).
3 TEMPORAL GRAPH ATTENTION NETWORK ARCHITECTURE
We first derive the mapping from time domain to the continuous differentiable functional domain the functional time encoding such that resulting formulation is compatible with self-attention mechanism as well as the backpropagation--aseed optimization frameworks. The same idea was explored in concurrent work (Xu al. 2019a). We then present the temporal graph attention layer and show how it can be naturally extended to incorporate the edge features.
3.1 FUNCTIONAL TIME ENCODING
Recall that our starting point is obtain a continuous functional mapping : T - Rdr from time domain to the ddddinsnsional vector space to replace the positional encoding in (1). Without loss of generality, we assume that the time domain can be represented by the interval starting from origin: T = [0, mmax] where fmax is determined by the observed data. For the inner-product self- attention in (2) often the "key" and 'query' matrices (K, Q) are given by identity or linear projection of Z. defined in (I), leading to terms that only involve inner-products between positional (time) encodings. Consider two time points t1, t2 and inner product between their functional encodings (#(t),, (tz)). Usually, the relative timespan, rather than the absolute value of time, reveals critical temporal information. Therefore, we are more interested in learning patterns related to the timespan of (/2 1, which should be ideally expressed by (11,,, ((12)) to be compatible with self-attention.
Formally, we define the temporal kernel T x T + with K(t1, t2) == (ottz), (t2)) and K((,, 12) (b4 12), V4,, la E T for some (mmxx mmax] - R. The temporal kernel is then
3

---

Published as a conference paper at ICLR 2020
cranslaton-iivariinnt,, since (C1 + c, + c) <b(11 t2) (2) for any constant c. Gener- ally speaking, functional learning is extremely complicated since operates on anfnite-dimensional spaces, but now we have transformed the problem into learning the temporal kernel Æ expressed by T. Nonetheless, we still need to figure out an explicit parameterization for & in order to conduct ef- ficient gradient-based optimization. Classical harmonic analysis theory, i.e. the Bochner's theorem, motivates our final solution. We point out that the temporal kernel K. is and continuous, since it defined via Gram matrix and the mapping continuous. Therefore, the kernel K. defined above satisfy the assumptions of the Bochner's 's theorem, which we state below. Theorem (Bochner's Theorem). A continuous, translation canslation-invariant kernel K(x, y) v y) on TR is positive definite if and only if there exists a non-negative measure on such that up is the Fourier transform of the measure.
(PSD)
Consequently, when scaled properly, our temporal kernel K. have the alternate expression:
K(11 (2) = (011,, 12) = eii(t- - -a) ( = EEw (4: (4))
(3)
where (t) caLit Since the kernel IC and the probability measure p(w) are real, we extract the real part of (3) and obtain:
(2( = IE,, cos(w((1 t2))] = E. [oos(wt)) cos(wst2) + sin(wt1) sin(wtz)]-
(4)
The above formulation suggests approximating the expectation by the Monte Carlo integral Rahimi & Recht 2008), i.e. (2) Rs Σ cos(w,;1) cos(w,;22) + sin(w,l1) sin(w)d2), with
ltd W1. Wd ~ p(w). Therefore, we propose the finite dimensional functional mapping to Rd as:
+ Bu(t)) = V I
V
sin
sin(wat)]
(5)
and it is easy to show that (Da(tt), (t2))) = (((t,tt)) t2). As matter of fact, prove the stochastic uniform convergence of (da(t)), (t())) to the underlying K((t,,t) t2) and shows that it takes only reasonable amount of samples to achieve proper estimation, which is stated in Claim 1.
Claim 1. Let p(w) be the corresponding probability measure stated in Bochner's Theorem for kernel function K. Suppose the feature map 4 is constructed as described above using samples (wi M then we only need d == [2 log oxtmaxx samples to have
sup (Pa(tt) (t(2 - k((1 < cwith any probability for Vc O, G,
where of is the second momentum with respect to p(w).
The proof is provided in supplement material.
By applying Bochner's theorem, we convert the problem of kernel learning to distribution learning, iee estimating the p(w) in Theorem 1. A straightforward solution to apply the reparameteriza- tion trick by using auxiliary random variables with known marginal distribution as in variational autoencoders (Kingma & Welling 2013). However, the reparameterization trick is often limited to certain distributions such as the 'local-scale' family, which may not be rich enough for our purpose. For instance, when p(w) is multimodal it is difficult to reconstruct the underlying distribution via di- rect reparameterizations. An alternate approach is to use the inverse cumulative distribution function (CDF) transformation. Rezende & Mohamed] (2015) propose using parameterized normalizing flow, i.e. sequence of invertible transtormation functions, approximate arbitrarily complicated CDF and efficiently sample from it. Dinh et al. (2016) further considers stacking bijective transforma- tions, known as affine coupling layer, to achieve more effective CDF estimation. The above methods learns the inverse CDF function F parameterized by flow-based networks and draw samples from the corresponding distribution. On the other hand, if we consider an non- non-parameterized ap- proach for estimating distribution, then learning F-1(() (.) and obtain d samples from it is equivalent to directly optimizing the (wi...., wa] in (4) as free model parameters. In practice, we find these two approaches to have highly comparable performances (see supplement material). Therefore focus on the non parameeeeti approach, since it is more serrameter-ffficcnn and has faster training speed (as no sampling during training is required).
The above functional time encoding is fully compatible with stlf-attention, thus they can replace the positional encodings in (T) and their parameters are jointly optimized as part of the whole model.
4

---

Published as a conference paper at ICLR 2020
(l - 1)th
4th
head
2 head
(c)
3 head
Wg
softmax
Q(1)
(c)
(
Zg(C)
(ta
Ag (9)
(c)
FFN
e(c
o(5)
2((
2x(()
Wx
(a 2
Wy
V(
Figure 2: The architecture of the 1hh TGAT layer with k 3 attention heads for node uo at time t.
3.2 TEMPORAL GRAPH ATTENTION LAYER
We use v, and x; E Fd to denote node and its raw node features. The proposed TGAT architecture depends solely the temporal graph attention layer (TGAT layer). In analogy GraphSAGE and GAT, the TGAT layer can be thought as local aggregation operator that takes the temporal neighborhood with their hidden representations (or features) as well as timestamps input, and the output is the time-aware representation for target node at any time point t. We denote the hidden representation output for node time from the 7th layer h (!) (t).
Similar to GAT, we perform the masked self-attention to take account of the structural in- formation (Veličković
al.] (017). For node to time ((o;() = {UI,..., JN such that the interaction between up and v; E WNon; 1). which takes place time 4, is prior to [ The input of TGAT layer is the neighborhood information Z (h(-")(t)) (fz)..... by ((-1)) (tx)) (tx)) and the target node information with some time point (hg (t),
consider its neighborhood
When = i.e. for the first layer, the inputs are just raw node features. The layer produces the
time-aware representation of target node vo at time t, denoted by hg (t), as its output. Due to the cunsslationinvariann assumption for the temporal kernel, 12)l and only care for the timespan.
alternatively use (t-th...., t-tx
as interaction times, since |4; ljl = (1 44)
In line with original self-attention mechanism, we first obtain the entity-temporal feature matrix as (t)) h (1 (t)l (0), (0), (t)) T t2)...., h (1- (tN)) Je, [x]] (or use sum)
(6)
and forward it to three different linear projections obtain the 'query', 'key" and 'valuc":
q()) [Z(]], Wo: K(I) [z(]] WK. K. V(() [Z((]] I:N Wr,
where Wo. W K. Wy (dd+dr)xd, are the weight matrices that employed to capture the interactions between time encoding and node features. For notation simplicity, in the fol- lowing discussion treat the dependence of the intermediate outputs on target time f as im- plicit. The attention weights far J. of the softmax function output in (2) is given by:
exp (qT..)/ E, exp (q*K.)) The attention weight a reveals how node attends to the fea- tures of node uo within the topological structure defined as (M(o;; t) after accounting for their inter- action time with Up. The self-attention therefore captures the temporal interactions with both node features and topological features and defines a local temporal aggregation operator on graph. The hidden representation for any node e; E (M;;t)) is given by: a, V.. The mechanism can be effec- tively shared across all nodes for any time point. We then take the row-wise sum from the above dot-product self-attention output the hidden neighborhood representations, i.e.
h())= = Attn ((tn) V(O) E Rd.
Node iú may have multiple interactions with at different time points. For the sake of presentation elarity, do not explicitly differentiate such recurring interactions in notations.
5

---

Published as a conference paper at ICLR 2020
To combine neighbourhood representation with the target node features, adopt the same practice from GraphSAGE and concatenate the neighbourhood representation with the target node's fea- ture vector Zg. We then pass it to feed-forward neural network to capture non-linear interactions between the features as in (Vaswani et al. 2017):
b (1) FFN (b()))x)) ReL.U (o0) W! +b²b) W + b,9
o! E (dd w E Rdxxd xd bgd E RRO, b E ER".
where hg (1) E Rd is the final output representing the time-aware node embedding at time & for the target node. Therefore, the TGAT layer be implemented for node classification task using the semi-supervised learning framework proposed in Kipf & Welling (2016a) as well as the link prediction task with the encoder-decoder framework summarized by Hamilton et al. (2017b).
Veličković et al. (2017) suggests that using multi-head attention improves performances and stabi- lizes training for GAT. For generalization purposes, we also show that the proposed TGAT layer can be easily extended to the multi- multi-hhadd setting. Consider the dot dot-product self-attention outputs from a total of l different heads, i.e. h(2) = Attn (6) (q(t). ((t), V(t)),
,,k. I....,k. We first concatenate the I neighborhood representations into combined vector and then carry out the same procedure:
( (t) FFN h (VII (1( (0)))))
Just like GraphSAGE, a single TGAT layer aggregates the localized one-hop neighborhood, and by stacking L TGAT layers the aggregation extends L hops. Similar to GAT, out approach does not restrict the size of neighborhood. We provide a graphical illustration of our TGAT layer in Figure
3.3 EXTENSION TO INCORPORATE EDGE FEATURES
We show that the TGAT layer can be naturally extended to handle edge features in message- passing fashion. Simonovsky & Komodakis (2017) and WWag et al. (2018b) modify classical spectral-based graph convolutional networks to incorporate edge features. Battaglia et al. (2018) propose general graph neural network frameworks where edges features can be processed. For tem- poral graphs, we consider the general setting where each dynamic edge is associated with a feature vector, i.e. the interaction between i and v/ at time t induces the feature vector x,, (t). To propagate edge features during the TGAT aggregation, we simply extend the (() (6) to:
Z(t) = [_....6'' (i((-)) (4:) (t.) (t - 1.)....] (or use summation),
such that the edge information is propagated to the target node's hidden representation, and then passed on to the next layer (if exists). The remaining structures stay the same as in Section 3.2
3.4 TEMPORAL SUB-GRAPH BATCHING
Stacking I. TGAT layers is equivalent aggregate over the L-hop neighborhood. For each L-hop sub-graph that constructed during the batch-wise training, all message passing directions must be aligned with the observed chronological orders. Unlike the non-temporal setting where each edge appears only once, in temporal graphs two node can have multiple interactions at different time points. Whether or not to allow loops that involve the target node should be judged case-by- case. Sampling from neighborhood, or known neighborhood dropout, may speed up and stabilize model training. For temporal graphs, neighborhood dropout can be carried uniformly or weighted by the inverse timespan such that more recent interactions has higher probability of being sampled.
3.5
COMPARISONS TO RELATED WORK
The functional time encoding technique and TGAT layer introduced in Section 3.1 and 3.2 solves several critical challenges, and the TGAT network intrinsically connects several prior methods.
Instead of cropping temporal graphs into sequence of snapshots or constructing time- constraint random walks, which inspired most the current temporal graph embedding methods, directly learn the functional representation of time. The proposed approach is

---

Published as a conference paper at ICLR 2020
motivated by and thus fully compatible with the well-established self-attention mechanism. Also, to the best of our knowledge, no previous work has discussed the temporal -eature interactions for temporal graphs, which is also considered in our approach.
The TGAT layer computationally efficient compared with RNN-based models, since the masked self-attention operation is parallclizable, as suggested by Vaswani et al. (2017). The per-batch time complexity of the TGAT layer with & heads and layers can be expressed as ((INN)) where N is the average neighborhood size, which is comparable to GAT. When using multi-head attention, the computation for each head can be parallelized as well.
The inference with TGAT' entirely inductive. With an explicit functional expression h(t)) for each node, the time-aware node embeddings can be easily inferred for any timestamp via single network forward pass. Similarity, whenever the graph is updated, the embed- dings for both unseen and observed nodes can be quickly inferred in inductive fashion similar to that of GraphSAGE, and the computations can be parallelized across all nodes.
GraphSAGE with mean pooling (Hamilton et al. 201 can be interpreted as special case of the proposed method, where the temporal neighborhood aggregated with equal attention coefficients. GAT is like the time-agnostic version of our approach but with different formulation for self-attention, as they refer to the work of Bahdaaa et al. (2014). We discuss the differences in detail in the Appendix. It is also straightforward to show our connections with the menory networks (Sukhbaatar et al. (0155) by thinking of the temporal neighborhoods memory. The techniques developed in our work may also help adapting GAT and GraphSAGE to temporal settings as we show in our experiments.
4 EXPERIMENT AND RESULTS
We test the performance of the proposed method against variety of strong baselines (adapted for temporal settings when possible) and competing approaches, for both the inductive and transductive tasks two benchmark and one large-scale industrial dataset.
4.1 DATASETS
Real-world temporal graphs consist of time-sensitive node interactions, evolving node labels as well as new nodes and edges. We choose the following datasets which contain all scenarios.
Reddit dataset We use the data from active users and their posts under subreddits, leading temporal graph with 1 11,000 nodes,~700,000 700,000 temporal edges and dynamic labels indicating whether a user is banned from posting. The user posts are transformed into edge feature vectors.
Wikipedia dataset We use the data from top edited pages and active users, yielding temporal graph ~9,300 nodes and around 160,000 temporal edges. Dynamic labels indicate users are temporarily banned from editing. The user edits are also treated as edge features.
Industrial dataset. We choose 70.000 popular products and 100,000 active customers as nodes from the online grocery shopping website"] and use the customer-product purchase as temporal edges (~2 million). The customers are tagged with labels indicating they have a recent interest in dietary products. Product features are given by the pre-trained product embeddings (Xu et al. 2020).
We do the chronological rein--alidation-tess test split with 70%- 15%- 15% according to node interaction timestamps. The dataset and preprocessing details are provided in the supplement material.
4.2 TRANSDUCTIVE AND INDUCTIVE LEARNING TASKS
Since the majority of temporal information is reflected via the timely interactions among nodes, we choose to use more revealing link prediction setup for training. Node classification is then treated as the downstream task using the obtained time-aware node embeddings as input.
Phtt:://saap.stanfeee www.totd..nddeeeeoooo edu/jodiiereddii.csv
http://snaapssaanfoot www.nooo..eduuuooiiccooooooccoce eddujooii/wikippdii....
/ walmart.com/
7

---

Published as a conference paper at ICLR 2020
Dataset
Reddit
Wikipedia
Industrial
Metric
Accuracy
AP
Accuracy
AP
Accuracy
AP
GAE
74.31 (0.5)
93.23 (0.3)
72.85 (0.7)
91.44 (0.1)
68.92 (0.3)
81.15 (0.2)
VAGE
74.19 (0.4)
92.92 (0.2)
78.01 (0.3)
91.34 (0.3)
67.81 (0.4)
80.87 (0.3)
DeepWalk
(0.6)
83.10 (0.5)
76.67 (0.5)
90.71 (0.6)
65.87 (0.3)
80.93 (0.2)
Node2vec
72.53 (0.4)
84.58 (0.5)
78.09 (0.4)
91.48 (0.3)
66.64 (0.3)
81.39 (0.3)
CTDNE
73.76
91.41 (0.3)
79.42 (0.4)
(0.5)
67.81 (0.3)
80,95 (0.5)
GAT
92.14 (0.2)
97.33 (0.2)
87.34 (0.3)
(0.2)
69.58 (0.4)
81.51 (0.2)
GAT+T
92.47 (0.2)
97.62 (0.2)
87.57 (0.2)
(0.44
70.15 (0.3)
82.66 (0.4)
GraphSAGE
92.31(0.2)
97.65 (0.2)
85.93 (0.3)
93.56 (0.3)
70.19 (0.2)
83.27 (0.3)
GraphSAGE+7
92.58 (0.2)
97.89 (0.3)
86.31 (0.3)
93.72 (0.3)
71.84 (0.3)
84.95 (0.)
Const-TGAT
91.39 (0.2)
97.86 (0.2)
86.03 (0.4)
(0.3)
68.52 (0.2)
81.91 (0.3)
TGAT
92.92 (0.3)
98.12 (0.2)
88.14 (0.2)
95.34 (0.1)
73.28 (0.2)
86.32 (0.1)
Transductive learning task results for predicting future edges of nodes that have been ob- served in training data. All results are converted to percentage by multiplying by 100, and the stan- dard deviations computed over ten runs (in parenthesis). The best and second-best results in each column are highlighted in bold font and underlined. GraphSAGE is short for GraphSAGE-LSTI
Table 1:
Dataset
Reddit
Wikipedia
Industrial
Metric
Accuracy
AP
Accuracy
AP
Accuracy
AP
GAT
89.86 (0.2)
95.37 (0.3)
82.36 (0.3)
91.27 (0.4)
68.28 (0.2)
79.93 (0.3)
GAT+T
90.44 (0.3)
96.31 (0.3)
84.82 (0.3)
93.57 (0.3)
69.51 (0.3)
81.68 (0.3)
GraphSAGE
89.43 (0.1)
96.27 (0.2)
82.43 (0.3)
91.09 (0.3)
67.49 (0.2)
80.54 (0.3)
GraphSAGEA
90.07 (0.2)
95.83 (0.2)
84.03 (0.4)
92.37 (0.5)
69.66 (0.3)
82.74 (0.3)
Const-TGAT
88.28 (0.3)
94.12 (0.2)
83.60 (0.4)
91.93 (0.3)
65.87 (0.3)
77.03 (0.4)
TGAT
90.73 (0.2)
96.62 (0.3)
85.35 (0.2)
93.99 (0.3)
72.08 (0.3) 84.99 (0.2)
Table 2: Inductive learning task results for predicting future edges of unseen nodes.
Transductive task examines embeddings of the nodes that have been observed in training, via the future link prediction task and the node classification. To avoid violating temporal constraints, we predict the links that strictly take place posterior all observations in the training data.
Inductive task examines the inductive learning capability using the inferred representations of un- seen nodes, by predicting the future links between unseen nodes and classify them based on their inferred embedding dynamically. We point out that it suffices to only consider the future sub-graph for unseen nodes since they are equivalent to new graphs under the non-temporal setting.
As for the evaluation metrics, in the link prediction tasks, we first sample an equal amount of nega- tive node pairs the positive links and then compute the average precision (AP) and classification accuracy. In the downstream node classification tasks, due to the label imbalance in the datasets, we employ the area under the ROC curve (AUC).
4.3 BASELINES
Transductive task: for link prediction of observed nodes, we choose the compare our approach with the state-of-the-art graph embedding methods: GAE and VGAE' (Kipl Welling 2016b). For complete comparisons, we also include the as well as the spectral-based DeepWalk model (Perozzi al.) 2014), using the same inner product decoder as GAF for link prediction. The CDTNE model based on the temporal random walk has been reported with superior performance on transductive learning tasks (Nguyen al. 2018), so we include CDTNE as the representative for temporal graph embedding approaches.
node2vee (Grover & Leskoved 2016)
Inductive task: few approaches are capable of managing inductive learning on graphs even in the non-temporal setting. As a consequence, we choose GraphSAGE and GAT as baselines after adapt- ing them to the temporal setting. In particular, we equip them with the same temporal uub-graph batching describe in Section 3.4 to maximize their usage temporal information. Also, we im- plement the extended version for the baselines to include edge features in the same way as ours (in Section 3.3 We experiment different aggregation functions for GraphSAGE, i.e. Graph-
8

---

Published as a conference paper at ICLR 2020
SAGE-mean, GraphSAGE-pon and GraphSAGE-LSTMM, In accordance with the original work of Hamilton et al. (2017a), GraphSAGE gives the best validation performance among the three approaches, which reasonable under temporal setting since LSTM aggregation takes account of the sequential information. Therefore we report the results of GraphSAGF-LLTTM.
In addition to the above baselines, we implement version of TGAT with all temporal attention weights set to equal value (Const-TGATT) Finally, to show that the superiority of our approach owes both the time encoding and the network architecture, we experiment with the enhanced GAT and GraphSAGE-menn by concatenating the proposed time encoding to the original features during temporal aggregations ( and GraphSAGE+T).
100
full
Dataset GAE
Reddit
Wikipedia
Industrial
58.39 (0.5)
74.85 (0.6)
76.59 (0.3)
pes-encode-leent re--enodde-ffue fixee
VGAE
57.98 (0.6)
73.67 (0.8)
75.38 (0.4)
25-
Auc scone
CTDNE
59.43 (0.6)
75.89 (0.5)
78,36 (0.5)
GAT
64.52 (0.5)
82.34 (0.8)
87.43 (0.4)
GAT+T
64.76 (0.6)
82.95 (0.7)
88.24 (0.5)
GraphSAGE
61.24 (0.6)
82.42 (0.7)
88.28 (0.3)
65-
GraphSAGE+T
62.31 (0.7)
82.87 (0.6)
89.81 (0.3)
Const TGAT
60.97 (0.5)
75.18 (0.7)
82.59 (0.6)
Reddt
Wilpedia
Industrial
TGAT
65.56 (0.7)
83.69 (0.7)
92.31 (0.3)
Dataset
Figure 3: Results node classification Table 3: Dynamic node classification task results, where the reported metric is the AUC.
task in the ablation study.
4.4 EXPERIMENT SETUP
We use the time-sensitive link prediction loss function for training the l-layer TGAT network:
l
Σ llg (o(- Ii,(t, - - B.E log (I((((
(8)
where the summation is over the observed edges and By that interact at time taj. and (() sigmoid function, Q is the number of negative samples and Pa(v) is the negative sampling distri- bution over the node space. As for tuning hyper-parameters, we fix the node embedding dimension and the time encoding dimension to be the original feature dimension for simplicity, and then select the number of TGAT layers from {1,2,3), the number of attention heads from (1.2,3,4.5). accord- ing to the link prediction AP score in the validation dataset. Although our method does not put restriction on the neighborhood size during aggregations, to speed up training. specially when using the multi-hop aggregations, we use neighborhood dropout (selected among p 10.1, 0.3, 0.5)) with the uniform sampling. During training, we use 0.0001 as learning rate for Reddit and Wikipedia dataset and 0.001 for the industrial dataset, with Glorot initialization and the Adam SGD optimizer. We do not experiment on applying regularization since our approach is parameter-efficient and only requires 2 ((dd + dy dd, + (d,, + d + dyd) parameters for each attention head, which is inde- pendent of the graph and neighborhood size. Using two TGAT layers and two attention heads with dropout rate 0.1 give the best validation performance. For inference, we inductively compute the embeddings for both the unseen and observed nodes at each time point that the graph evolves, or when the node labels are updated. We then use these embeddings as features for the future link prediction and dynamic node classifications with multilayer perceptron.
(.) is the
We further conduct ablation study demonstrate the effectiveness of the proposed functional time encoding approach. We experiment on abandoning time encoding or replacing it with the original positional encoding (both fixed and learnt). We also compare the uniform neighborhood dropout to sampling with inverse timespan (where the recent edges are more likely to be sampled), which is provided in supplement material along with other implementation details and setups for baselines.
4.5 RESULTS
The results in Table and Table demonstrates T the of-te-of-the-ar the-art performances of our approach on both transductive and inductive learning tasks. In the inductive learning task, our TGAT network sig- nificantly improves upon the the upgraded GraphSAGF-LLSTI and GAT' in accuracy and average

---

Published as a conference paper at ICLR 2020
precision by at least 5 % for both metrics, and in the transductive learning task TGAT consistently outperforms all baselines across datasets. While GAT+T and GraphSAGE+T slightly outperform or tie with GAT and CraphSAGE-LSTNN, they are nevertheless outperformed by our approach. On one hand, the results suggest that the time encoding have potential to extend non-temporal graph representation learning methods to temporal settings. On the other, note that the time encoding still works the best with our network architecture which is designed for temporal graphs. Over- all, the results demonstrate the superiority of our approach in learning representations on temporal graphs over prior models. We also see the benefits from assigning temporal attention weights to neighboring nodes, where GAT significantly outperforms the ToAst-TGAT in all three tasks. The dynamic node classification outcome (in Table 3 further suggests the usefulness of our time-aware node embeddings for downstream tasks as they surpass all the baselines. The ablation study results of Figure successfully reveals the effectiveness of the proposed functional time encoding approach in capturing temporal signals as it outperforms the positional encoding counterparts.
4.6 ATTENTION ANALYSIS
To shed some insights into the temporal signals captured by the proposed TGAT, we analyze the pattern of the attention weights {t) as functions of both time t and node pairs (i.j) in the inference stage. Firstly, we analyze how the attention weights change with respect to the timespans of previous interactions, by plotting the attention weights { (Rig((i)) )gg E Wuy; fny) fufaa (oas(ty))))))) (big lk E N(u } } against the timespans {t,, bu t,, | when predicting the link for (e,, Vy, tiy) E (Figure 4p). This gives us an empirical estimation on the a (At), where a smaller At means more recent interaction. Secondly, we analyze how the topological structures affect the attention weights as time clapses. Specifically, finding out what attention weights the model put on the neighbouring nodes with different number of reoccurrences. Since the functional forms of all (.)) are fixed after training. in different target time and then record their value on neighbouring nodes with different number of occurrences (Figure 4p). From Figure 4 observe that TGAT captures the pattern of having less attention on more distant interactions in all three datasets. In Figure/4.. it is obvious that when predicting more future interaction, TGAT will consider neighbouring nodes who have higher number of occurrences of more importance. The patterns of the attention weights are meaningful, since the more recent and repeated actions often have larger influence on users' future interests.
focus on the topological structure of the recurring neighbours, by
able to feed
(a) 0.4
(b)
Dakend
Roccurienoos
Wiccpeds
Raddd:
one
Induatrill
Deo
0.20
four
0.18
0.18
0.12
100
200
3000
500
Timespon
Timespan (hour) the Industrial datisee
Figure 4: Attention weight analysis. We apply the Loess smoothing method for visualization.
CONCLUSION AND FUTURE WORK
We introduce novel time-aware graph attention network for inductive representation learning on temporal graphs. We adapt the self-attention mechanism to handle the continuous time by proposing a recoreticlll-grrundee functional time encoding. Theoretical and experimental analysis demon- strate the effectiivneess of our approach for capturing temporal- signals in terms of both node and topological features on temporal graphs. Self-attention mechanism often provides useful model interpretations (Vaswani et al. 2017), which is an important direction of our future work. Develop- ing tools to visualize the evolving graph dynamics and temporal representations efficiently is another important direction for both research and application. Also, the functional time encoding technique has huge potential for adapting other deep learning methods to the temporal graph domain.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint (4XXi::400.0444 2014.
Peter W Battaglia, Jessica B Hamrick. Victor Bapst, Alvaro Gonzalz-Gozzalzz, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.0111 01261,
2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances neural information processing systems, pp. 3844-3852, 2016.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real nvp. arXiv preprint 1605.08800 2016.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with Py Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Palash Goyal, Nitin Kamra, Xinran He, and Yan Liu. Dyngem: Deep embedding method for dy- namic graphs. arXiv preprint arXiv: 1273, 2018.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pp. 855-864. ACM, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs.
In Advances Neural Information Processing Systems, pp. 1024-1034 2017a.
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. arXiv preprint 1709.0/709.05588 2017b.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv preprint arXiv:1506.0516. 2015.
Diederik Kingma and Max Welling.
Auto-encoding variational bayes. arXiv preprint
arXiv:1312.6114, 2013.
Thomas N Kipf and Max Welling. Semi-super classification with graph convolutional net- works. arXiv preprint 16Xiv:1609.02900 2016a.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. 1rXiv:1611.07308, 2016b.
arXiv preprint
Taisong Li, Jiawei Zhang, S Yu Philip, Yan Zhang, and Yonghong Yan. Deep dynamic network embedding for link prediction. IEEE Access, 6:29219-29230, 2018
Lynn H Loomis. Introduction to abstract harmonic analysis. Courier Corporation, 2013.
Yao Ma, Ziyi Guo, Eric Zhao Zhaochun Ren, and Dawei Yin Jiliang Tang. Streaming graph neural networks. arXiv preprint arXiv: 181.:1081....... 2018.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5115- 5124, 2017.
Giang Hoang Nguyen, John Boaz Lee, Ryan A Rossi, Nesreen K Ahmed, Funyee Koh, and Sungchul Kim. Continuous time dynamic network embeddings. In Companion Proceedings of the The Web Conference 2018, pp. 969-976. International World Wide Web Conferences Steering Committee, 2018
James W Pennebaker, Martha Francis, and Roger J Booth. Linguistic inquiry and word count: Liwe 2001. Mahway: Lawrence Erlhaum Associates, 71(2001):2011, 2001.

---

Published as a conference paper at ICLR 2020
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710. ACM, 2014.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems, pp. 1177-1184, 2008.
Mahmudur Rahman, Tanay Kumar Saha, Mohammad AI Hasan, Kevin S Xu, and Chandan Reddy. Dylink2vec: Effective feature representation for link prediction in dynamic networks. arXiv preprint urXiv:1804.057755 2018.
Danilo Jimenez Rezende and Shakir Mohamed. Variational inference with normalizing flows. arXiv preprint arXiv: 055700, 2015.
Martin Simonovsky and Nikos Komodakis. Dynamic adge-conditioned filters in convolutional neu- ral networks on graphs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3693-3702, 2017.
Sainbayar Sukhbaatar, Jason Weston, Rob Fergus, et al. End-to-end memory networks. In Advances in nearal information processing systems, pp. 2440-2448, 2015.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. Proceedings of the 24th international conference on world wide web, pp. 1067-1077. International World Wide Web Conferences Steering Committee, 2015.
Rakshit Trivedi, Mehrdad Farajtahar, Prasenjeet Biswal, and Hongyuan Zha. Representation learn- ing over dynamic graphs. arXiv preprint arXiv:/803.00 /803,04051, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.1090. 2017.
Daixin Wang, Peng Cui, and Wenwu Zhu, Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pp- 1225-1234. ACM, 2016.
Jizhe Wang, Pipei Huang, Huan Zhao, Zhibo Zhang, Binqiang Zhao, and Dik Lun Lee. Billion-scale commodity embedding for e-commerce recommendation in alibaba. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 839-8889-00 848. ACM, 2018a.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph cnn for learning on point clouds. arXiv preprint arXiv: /8010022, 2018b.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Self-attention with functional time representation learning. In Advances in Neural Information Processing Systems, pp. 15889-15899, 2019a
Da Xu, Chuanwei Ruan, Kamiya Motwani, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Generative graph convolutional network for growing graphs. In ICASSP 2019-2019 IEEE In- ternational Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3167-3171. IEEE, 2019b.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Product knowledge graph embedding for e-commerce. In Proceedings of the 13th International Conference Web Search and Data Mining, pp. 672-680, 2020.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974- 983. ACM, 2018
12

---

Published as a conference paper at ICLR 2020
A APPENDIX
A.1
PROOF FOR CLAIM
Proof. The proof also shown our concurrent work Xu et (2019a). We also provide it here for completeness. To prove the results in Claim 1, we alternatively show that under the same condition,
Pr( sup 1 (t,) (t22 K((t,, 2 2) - 40, max erp( NNET
de
32
((1) (8 The goal is derive uniform upper bound for s(1,, (2) - (() By assumption S(4, (2) is an unbiased estimator for KC(1, 42), i.e.
Define the score (2),
E[S([1: (2) = ((4,42). Due to the translation-invarian property of S and K, let A())
s(t1, 12) - K((t,,t)), 12), where = to for all f E [0, Also we define s(1 (2) ==
S(11,t2) Therefore E t-taax maax]. and we use t E T as the shorthand notation. The LHS in (1) now becomes Pr(supreñ
A()) 2 2).
Note that T S - with T; [-txax + 2dlmax maxx + 2(1+1)mma for i 1....,
N. So
O Ti is finite cover of T. Define t, -inax we have
(264 1841))mmx then for any t Tú, i ,,...,N
[a(t)| = (t) (t,,) + A(t,)
< (t) A(t)) + (A()))
< Lalt - t4| + [t,)
(10)
2lmax
S LA
N A(()):
where LA m || [+(I)] (since A is differentiable) with the maximum achieved at t*, So may bound the two events separately.
For (t:)) simply notice that trigeometric functions are bounded between [-1, and therefore
-1 I (1)) (122 S The Hoeffding's inequality for bounded random variables immediately
gives us:
Pr(IA(()) > 5) S 2exp(
de?
16
So applying the Hoeffding seffidiing-yyeeeaee union bound to the finite cover gives
de²
5) S 2N exp(
(1I)
16
For the other event we first apply Markov inequality and obtain:
PL(LA 2fmax
2 .) Pr(Lo 4fmax
eN
4tmax E E[L3]
(12)
N
e.V
Also, since E(s(t: - t2)) = wtt1 12). we have
F[T2] = ((t)) 2 V(())) FIIV = oz.
(13)
where of is the second momentum with respect to p(w). Combining
12 and gives us:
dea
4
Pr( Pr( sup (())) 2 S 2N exp(
(14)
16
cN
It is straightforward to examine that the RHS of convex function N and is minimized by N =pp 2taes erp(
Plug N back to and obtain (9). We then solve for d according to 9 and obtain the results in Claim 1.
de? 37
13

---

Published as a conference paper at ICLR 2020
A.2 COMPARISONS BETWEEN THE ATTENTION MECHANISM OF TGAT AND GAT
In this part, we provide detailed comparisons between the attention mechanism employed by our proposed TGAT and the GAT proposed by Veličković et al. 2017). Other than the obvious fact that GAT does not handle temporal information, the main difference lies in the formulation of attention weights. While GAT depends on the attention mechanism proposed by [Bahdanau et al. (2014), our architecture refers to the self-attention mechanism of Vaswani et al. (2017). Firstly, the attention mechanism used by GAT does not involve the notions of "query'. "key" and "value" nor the dot- product formulation introduced in (2) As consequence, the attention weight between node and its neighbor Uj is computed via
exp (LeakyReL.(a7/Whh] [hh,])
0ij
EKENTO.) exp (LeakyReL.U(at [Wh,| (hhhl)Whel))
where is weight vector, W is weight matrix, M(vs)) is the neighorhood set for node and h, is the hidden representation of node v, is then obvious that their computation of okz is very different from our approach. In TGAT, after expanding the expressions in Section the attention weight is computed by:
exp
(t- (B, (t-t)] (x) W)))
Oriy (1) EnEN(ONN)) exp (4,) 4) ((h
Intuitively speaking, the attention mechanism of GAT relies on the parameter vector a and the LeakyReL.U() capture the hidden factor interactions between entities in the sequence, while use the linear transformation followed by the dot-product to capture pair-wise interactions of the hidden factors between entities and the time embeddings. The dot-product formulation is important for our approach. From the theoretical perspective, the time encoding functional form is derived according to the notion of temporal kernel K. and its inner- mnnerproduct decomposition (Section 33. As for the practical performances, we see from Table 2 and 3 that even after we equip GAT with the same time encoding, the performance is still inferior to our TGAT.
A.3 DETAILS ON DATASETS AND PREPROCESSING
Reddit dataset: this benchmark dataset contains users interacting with subreddits by posting under the subreddits. The timestamps tell us when the user makes the posts. The dataset uses the posts made a one-month span, and selects the most active users and subreddits as nodes, giving a total of 11,000 nodes and around 700,000 temporal edges. The user posts have textual features that are transformed into a 172-dimensional vector representing under the linguistic inquiry and word count (LIWC) categories (Pennebaker al., 2001). The dynamic binary labels indicate if user is banned from posting under a subreddit. Since node features are not provided in the original dataset, we use the all-zero vector instead.
Wikipedia dataset: the dataset also collects one-month of interactions induced by users' editing the Wikipedia pages. The the top edited pages and active users are considered, leading 99,300 nodes and around 160,000 temporal edges. Similar to the Reddit dataset, we also have the ground-truth dynamic labels on whether user is banned from editing Wikipedia page. User edits consist of the textual features and are also converted into 172-dimensional LIWC feature vectors. Node features are also not provided, we also use the all-zero vector as well.
Industrial dataset: we obtain the large-scale customer-produet interaction graph from the online grocery shopping platform grocery ry . wa 1 ma rt com. We select 700,000 most popular products and 100,000 active customers nodes and use the customer- pustomer-proouuct purchase interactions over one-month period as temporal edges (~~2 million). Each purchase interaction is timestamped, which use construct the temporal graph. The customers are labelled with business tags, indicating if they are interested in dietary products according to their most recent purchase records. Each product node possesses contextual features containing their name, brand, categories and short description. The previous LIWC categories no longer apply since the product contextual features are not natural sentences. We product embedding approach (Xu 2020) to embed each product's contextual
14

---

Published as a conference paper at ICLR 2020
Reddit
Wikipedia 9,227
Industrial
# Nodes
11,000
170,243
Edges
672,447
157,474
2,135,762
# Feature dimension
172
172
100
LIWC category
LIWC category
document
Feature type
vector
vector
embeddings
Timespan
30 days
30 days
30 days
% Training nodes
90%
90%
90%
% Unseen nodes
10%
10%
10%
% Training edges
~67%
~65%
~64
% Future edges between
277
28%
29%
observed nodes
% Future edges between unseen nodes
~6
~7%
~7%
# Nodes with dynamic
366
217
5,236
labels
Label type
binary banned from posting
binary banned from editting
binary interested in dietary products
Positive label meaning
Table 4: Data statistics for the three datasets. Since sample a proportion of unseen nodes, the percentage of the edge statistics reported here are approximations.
features into 100-dimensional vector space as preprocessing. The user nodes and edges do not possess features.
We then split the temporal graphs chronologically into 70%-15%-155% for training, validation and testing according to the time epochs of edges, as illustrated in Figure the Reddit dataset. Since all three datasets have relatively stationary edge count distribution over time, using the 70 and 85 percentile time points to split the dataset results in approximately 10% of total edges, as suggested by Figure
Reddit Dataset
Train
Validate:
Test
1200
800
Count
400
200
500000
1000000
1500000
2000000
2500000
Time (Linux epoch)
Figure 5: The distribution of temporal edge count for the Reddit dataset, and the illustration on the vain-validation-test splitting.
To ensure that an appropriate amount of future edges among the unseen nodes will show up during validation and testing, for each dataset, we randomly sample 10% of nodes, mask them during training and treat them unseen nodes by only considering their interactions in validation and testing period. This manipulation is necessary since the new nodes that show up during validation and testing period may not have much interaction among themselves. The statistics for the three datasets are summarized in T
Preprocessing.
For the Node2vec and Deep Walk baselines who only take static graphs as input, the graph is con- structed using all edges in training data regardless of temporal information. For DeepWalk, we treat
15

---

Published as a conference paper at ICLR 2020
the recurrent edges as appearing only once, so the graph is unweighted. Although our approach han- dles both directed and undirected graphs, for the sake of training stability of the baselines, we treat the graphs undirected. For Node2vec, construct the weighted graph. For all three datasets, the obtained graphs in both cases are undirected and do not have isolated nodes. Since we choose from active users and popular items, the graphs are all connected.
use the count of recurrent edges their weights and
For the graph convolutional network baselines, i.e. GAE and VGAE, we construct the same undi- rected weighted graph as for Node2vec. Since GAE and VGAE do not take edge features as input, we use the posts/edits as user node features. For each user in Reddit and Wikipedia dataset, we take the average of their post/edit feature vectors as the node feature. For the industrial dataset where user features are not available, we use the all-zero feature vector instead.
As for the downstream dynamic node classification task, we use the same training, validation and testing dataset as above. Since we aim at predicting the dynamic node labels, for Reddit and Wikipedia dataset we predict if the user node is banned and for the industrial dataset we predict the customers' business labels, at different time points. Due to the label imbalance, in each of the batch when training for the node label classifier, we conduct stratified sampling such that the label distributions are similar across batches.
A.4 EXPERIMENT SETUP FOR BASELINES
For all baselines, we set the node embedding dimension to d = 100 to keep in accordance with our approach.
Transductive baselines.
Since Node2vec and DeepWalk do not provide room for task-specific manipulation or hacking, we do not modify their default loss function and input format. For both approaches, we select the num- ber of walks among (60.80,100) and the walk-length among (20,30,40) according to the validation AP. Setting number of walks=80 and walk-length=30 give slightly better validation performance compared to others for both approaches. Notice that both Node2vec and DeepWall use the sigmoid function with embedding inner-product as the decoder to predict neighborhood probabilities. So when predicting whether v; and Vj will interact in the future, we use of o-z2,2,) as the score, where 2; and zj are the node embeddings. Notice that Node2vec has the extra hyper-parameter which controls the likelihood of immediately revisiting a node in the walk and interpolation between breadth-fire first strategy and depth-first first strategy. After selecting the optimal number of walks and walk- length under p = and = 1, we further tune the different values of in {0.22.04.0.66 1.00 while fixing q 1. According validation, p 0.6 and 0.8 give comparable optimal performance.
and g
For the GAE and VGAE baselines, we experiment on using one, two and three graph convolutional layers the encoder (Kipf & Welling 201 and use the ReLU(.) as the activation function. By referencing the official implementation, we also set the dimension of hidden layers to 200. Sim- ilar to previous findings, using two layers gives significant performances Adding the third layer, on the other hand, shows almost identical results for both models. Therefore the results reported are based on two-layer GCN as the encoder. For GAE, we use the standard inner-product decoder as our approach and optimize over the reconstruction loss, and for VGAF, we restrict the Gaussian latent factor space (Kipf & Welling 20166). Since we have eliminated the tem- poral information when constructing the input, we find that the optimal arperpparameters selected according to the tuning have similar patterns as in the previous non-temporal settings.
using only one layer.
For the temporal network embedding model CTDNE, the walk length for the temporal random walk is also selected among [60,80,100), where setting walk length to 80 gives slightly better validation outcome. The original paper considers several temporal edge selection (sampling) methods (uni- form, linear and exponential) and finds uniform sampling with best performances (Nguyen et al. 2018). Since our setting is similar to theirs, we adopt the uniform sampling approach.
Inductive baselines.
For the GraphSAGE and GAT baselines, mentioned before, we train the models in an identical way as our approach with the temporal subgraph batching, despite several slight differences. Firstly, the aggregation layers in GraphSAGE usually considers fixed neighborhood size via sampling.
16

---

Published as a conference paper at ICLR 2020
whereas approach can take an arbitrary neighborhood as input. Therefore, we only consider the most recent dsample edges during each aggregation for all layers, and we find dsample = 20 gives the best performance among {10,15,20,25) Secondly, GAT implements uniform neighborhood dropout, We also experiment with the inverse timespan sampling for neighhorhood dropout, and find that it gives slightly better performances but the cost of computational efficiency, especially for large graphs. We consider aggregating over one, two and three-hop neighborhood for both GAT and GraphSAGE. When working with three hops, we only experiment on GraphSAGE with the mean pooling aggregation. In general, using two hops gives comparable performance to using three hops. Notice that computations with three-hop are costly, since the number of edges during aggregation increase exponentially to the number of hops. Thus we stick to using two hops for GraphSAGE, GAT and our approach. is worth mentioning that when implementing GraphSAGE-LSTMM, the input neighborhood sequences of LSTM are also ordered by their interaction time.
Node classification with baselines.
The dynamic node classification with GraphSAGE and GAT can be conducted similarity to our approach, where we inductively compute the most up-to-date node embeddings and then input them as features to an MLP classifier. For the transductive baselines, it is not reasonable to predict the dynamic node labels with only the fixed node embeddings. Instead, we combine the node embedding with the other node embedding it is interacting with when the label changes, c.g. combine the user embedding with the Wikipedia page embedding that the user attempts on editing when the system bans the user. To combine the pair of node embeddings, we experimented summation, concatenation and bi-linear transformation. Under summation and concatenation, the combined embeddings are then used as input to an MLP classifier, where the bi-linear transformation directly outputs scores for classification. The validation outcomes suggest that using concatenation with MLP yields the best performance.
A.5 IMPLEMENTATION DETAILS
Training. We implement Node2vec using the official C code on 16-core Linux server with 500
Gb memory. DeepWalk is implemented with the official python code o geometric library for implementing the GAE and VGAE baselines (Fey & Lenssen 2019). To accommodate the temporal setting and incorporate edges features, we develop off-the-shelf imple- mentation for Gra and GAT in PyTorch by referencing their original implementations 7 We also implement our model using PyTorch. All the deep learning models are trained on ma- chine with one Tesla V100 GPU. We use the Glorot initialization and the Adam SGD optimizer for all models, and apply the early-stopping strategy during training where we terminate the training process if the validation AP score does not improve for 10 epochs.
We refer to the Py PyTorch
Downstream node classification. As we discussed before, we use the three-layer MLP as classifier and the (combined) node embeddings as input features from all the experimented approaches, for all three datasets. The MI.P is trained with the Glorot initialization and the Adam SGD optimizer in PoTorch as well. The & regularization parameter À is selected in {0.001, 0.01, 0.05, 0.1, 0.2) case-by-case during training. The early-stopping strategy is also employed.
A.6 SENSITIVITY ANALYSIS AND EXTRA ABLATION STUDY
Firstly, we focus on the output node embedding dimension as well as the functional time encoding dimension in this sensitivity analysis. The reported results are averaged over five runs. We experi- ment on d E {60. 80, 100, 120, 140) and dr E {60, 80, 100, 120, 140), and the results are reported in Figure 7 and 7c The remaining model setups reported in Section 4.4 are untouched when vary- ing d or d7. We observe slightly better outcome when increasing either d or dr on the industrial dataset. The patterns on Reddit and Wikipedia dataset are almost identical.
Secondly, we compare between the two methods of learning functional encoding, i.e. using flow- based model or using the non-parametric method introduced in Section 3.1 We experiment on two
17

---

Published as a conference paper at ICLR 2020
100
100
06
90
Accuracy
85
Accuracy
85
Roddk
Wiripedia Dataset
Industrial
ReddE
Wikpedia
Industrial
Dataset
(a) Comparison between uniform and inverse timespan weighted sampling the link predie- tion task
(b) Comparison between three different ways of learning the functional time encoding, link pre- diction task.
Figure 6: Extra ablation study.
80.0
77.5
75.0
Accuracy
725
Accuracy
70.0
67.5
65.0
65.0
625
02.5
60.0
60.0
120
Node embedding dimension
Time embedding dimension
(a) Sensitivity analysis on node embeddings di-
(b) Sensitivity analysis on time embeddings di- mension.
mension.
0.74
Accuracy
0.70
Average Precision
0.88
Number of heads
0.86
0.84
Numbor heads
#layers one layer (hop)
two leyers (hops)
(c) Sensitivity analysis on number of attention heads and layers (hops) with d 100 and dr 100.
Figure 7: Sensitivity analysis on the Industrial dataset.
flow-based state-of-the-an art CDF learning method: normalizing flow (Rezende & Mohamed, 2015)
and RealNVP (Dinh et al. (016)) We use the default model setups and hyper-parameters in their reference implementations 1 We provide the results in Figure 6b] As we mentioned before, using flow-based models leads to highly comparable outcomes the non-parametric approach, but they require longer training time since they implement sampling during each training batch. However,
18

---

Published as a conference paper at ICLR 2020
is possible that carefully-tune -uune flow-based models can lead to nontrivial improvements, which leave to the future work.
Finally, provide sensitivity analysis on the number of attention heads and layers for TGAT. Recall that by stacking two layers TGAT we are aggregating information from the two-hop neighbour- hood. For both accuracy and AP, using three-head attention and two-layers gives the best outcome. In general, the results are relatively stable to the number of heads, and stacking two layers leads to significant improvements compared with using only single layer.
The ablation study for comparing between uniform neighborhood dropout and sampling with inverse timespan is given in Figure 6a The experiments carried out under the same setting which we reported in Section 4.4 We see that using the inverse timespan sampling gives slightly worse performances. This within expectation since uniform sampling has advantage in capturing the recurrent patterns, which can be important for predicting user actions. On the other hand, the results also suggest the effectiveness of the proposed time encoding for capturing such temporal patterns. Moreover, point out that using the inverse timespan sampling slows down training, particularly large graphs where weighted sampling is conducted within a large number of nodes for each training batch construction. Nonetheless, inverse timespan sampling can help capturing the more recent interactions which may be more useful for certain tasks. Therefore, we suggest to choose the neighborhood dropout method according to the specific use cases.
19


Reviews:
[{"review_id": "S1gCZwh2Kr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The major contribution of this paper is the use of random Fourier features as temporal (positional) encoding for dynamic graphs. These encodings are concatenated with standard node embeddings in transformer-like attention calculations for graph message passing. The reader finds that the proposed approach is interesting.\n\nExperimental results are also favorable.\n\nConcern: Whereas the use of random Fourier features (RFF) is well justified, a limitation is that it is based on a stationarity assumption. Thus, it may be less applicable to nonstationary structural changes. To cope with nonstationarity, a straightforward idea is to parameterize the temporal encoding by using neural networks rather than RFF. In the authors' approach, the RFF is in a sense parameterized, because the frequencies omega are learned. Nevertheless, the stationarity limitation persists.\n\nQuestion: In the ablation study, what exactly is \"the original positional encoding\"? Are they learned embedding vectors? Since the authors consider continuous time rather than discrete time, how many embedding vectors are there?\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJgpzq645S", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed the temporal graph attention layer which aggregates in-hop features with self-attention and incorporates temporal information with Fourier based relative positional encoding. This idea is novel in GCN field. Experimental results demonstrate that the TGAT which adds temporal encoding outperforms the other methods. Overall this paper addressed its core ideas clearly and made proper experiments and analysis to demonstrate the superiority against existing counterparts.\n\nThere are some things need to be further answered. The baselines compared in this paper seems to be too weak. For example, how does T-GraphSage (GraphSAGE+Temporal encoding) work? How does the single-head variant of TGAT work? How does the original GAT work plus temporal encoding (as I notice TGAT uses self-attention which is similar but may not be equivalent to original GAT attention formulation, are they equivalent or not?)", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1e4OGa6tB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper addresses the problem of representation learning for temporal graphs. That is, graphs where the topology can evolve over time. The contribution is a temporal graph attention (TGAT) layer aims to exploit learned temporal dynamics of graph evolution in tasks such as node classification and link prediction. This TGAT layer can work in an inductive manner unlike much prior work which is restricted to the transduction setting. Specifically, a temporal-kernel is introduced to generate time-related features, and incorporated into the self-attention mechanism. The results on some standard and new graph-structured benchmarks show improved performance vs a variety of baselines in both transduction and inductive settings. \n\nPros: \n+ Dynamic graphs are an important but challenging data structure for many problems. Improved methods in this area are welcome. \n+ Dealing with the inductive setting is an important advantage. \n+ Clear performance improvements on prior state of the art is visible in both transductive+inductive settings and node+edge related tasks.\n\nCons+Questions:\n1. Technical significance: Some theory is presented to underpin the approach, but in practice it seems to involve concatenating or adding temporal kernels element-wise to the features already used by GAT. In terms of implementation the concatenation in Eq 6 seems to be the only major change to GAT. I’m not sure if this is a major advance.  \n2. Insight. The presented method apparently improves on prior work by learning something about temporal evolution and exploiting it in graph-prediction tasks. But it's currently rather black-box. It would be better if some insight could be extracted about *what* this actually learns. What kind of temporal trends exist in the data that this method has learned? And how are they exploited in by the prediction tasks?\n3. Writing. The English is rather flaky throughout. One particular recurring frustration is the use of the term “architect” which seems wrong. Probably “architecture” is the correct alternative. \n4. Clarity of explanation. The paper is rather hard to follow and ambiguous. A few specific things that are not explained so well: \n4.1. Eq 1+2 is not a sufficiently clear and self-contained recap of prior work. \n4.2. Symbol d_T used at the start of Sec 3.1 seems to be used without prior definition making it hard to connect to previous Eq1+2. \n4.3 The claim made about alternative approaches (Pg4) “Reparameterization is only applicable to local-scale distribution family, which is not rich enough”. Seems both too vague and unjustified. \n4.4 The relationship between $t_i$ and the neighbours of the target node in Eq. 6 is not very clear.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The major contribution of this paper is the use of random Fourier features as temporal (positional) encoding for dynamic graphs. The reviewers all find the proposed method interesting, and believes that this is a paper with reasonable contributions. One comment pointed out that the connection between Time2Vec and harmonic analysis has been discussed in the previous work, and we suggest the authors to include this discussion/comparison in the paper.
Decision: Accept (Poster)