Dynamic Graph Representation Learning via Graph Transformer Networks
Authors: Weilin Cong
Yanhong Wu
Yuandong Tian
Mengting Gu
Yinglong Xia
Mehrdad Mahdavi
Chun-cheng Jason Chen
Venue: ICLR 2022 Submitted (2022)
Keywords: dynamic graphs
graph neural networks
graph representation learning
transformers
graph transformers

Abstract: Dynamic graph representation learning is an important task with widespread applications. Previous methods on dynamic graph learning are usually sensitive to noisy graph information such as missing or spurious connections, which can yield degenerated performance and generalization. To overcome this challenge, we propose a Transformer-based dynamic graph learning method named Dynamic Graph Transformer (DGT) with spatial-temporal encoding to effectively learn graph topology and capture implicit links. To improve the generalization ability, we introduce two complementary self-supervised pre-training tasks and show that jointly optimizing the two pre-training tasks results in a smaller Bayesian error rate via an information-theoretic analysis. We also propose a temporal-union graph structure and a target-context node sampling strategy for efficient and scalable training. Extensive experiments on real-world datasets illustrate that DGT presents superior performance compared with several state-of-the-art baselines.

Under review as a conference paper at ICLR 2022
DYNAMIC GRAPH REPRESENTATION LEARNING VIA GRAPH TRANSFORMER NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Dynamic graph representation learning is an important task with widespread ap- plications. Previous methods on dynamic graph learning are usually sensitive to noisy graph information such as missing spurious connections, which can yield degenerated performance and generalization. To overcome this challenge, we propose a Transformer-basee dynamic graph learning method named Dynamic Graph Transformer (DGT) with spatial-temporal encoding to effectively learn graph topology and capture implicit links. To improve the generalization ability, we introduce two complementary self-supervised pre-training tasks and show that jointly optimizing the pre-training tasks results in smaller Bayesian error rate via an information-theoredl analysis. We also propose a remporal-unioe graph structure and larget-context node sampling strategy for an efficient and scalable training. Extensive experiments on real-world datasets illustrate that DGT presents superior performance compared with several state-of-the-ee baselines.
INTRODUCTION
In recent years, graph representation learning has been recognized as fundamental learning problem and has received much attention due to its widespread use in various domains, including social network analysis (Kipf & Welling, 2017; Hamilton al., 2017), traffic prediction (Cui al., 2019; Rahimi et al., 2018). knowledge graphs (Wang et al., 2019a;b), drug discovery (Do et al., 2019; Duvenaud et al., 2015), and recommendation systems (Berg al., 2017: Ying et al., 2018). Most existing graph representation learning work focuses on static graphs. However, real-world graphs are intrinsically dynamic where nodes and edges can appear and disappear over time. This dynamic nature of real-world graphs motivates dynamic graph representation learning methods that can model temporal evolutionary patterns and accurately predict node properties and future edges.
Recently, several attempts (Sankar et al., 2018; Pareja et al., 2020; Goyal et al., 2018) have been made to generalize graph learning algorithms from static graphs to dynamic graphs by first learning node representations each static graph snapshot then aggregating these representations from the temporal dimension. However, these methods are vulnerable to noisy information such as missing spurious links. This is due to the ineffective message aggregation over unrelated neighbors from noisy connections. The temporal aggregation makes this issue severe by further carrying the noise information over time. Over-relying on graph structures makes the model sensitive noisy input and can significantly affect downstream task accuracy. A remedy is to consider the input graph as fully connected and learn a graph topology by assigning lower weights to task-irrelevant edges during training (Devlin et al., 2019). However, completely ignoring the graph structure makes the optimization inefficient because the model has estimate the underlying graph structure while learn model parameters at the same time. To resolve the above challenges, we propose a Transformer-basee dynamic graph learning method named Dynamic Graph Transformer (DGT) that can "leverage underlying graph structures" and "capture implicit edge connections" to balance this trade-off.
Transformers (Vaswani et al., 2017), designed to automatically capture the inter-dependencies between tokens in a sequence, have been successfully applied in several domains such as Natural Language Processing (Devlin et al., 2019; Brown et al., 2020) and Computer Vision (Dosovitskiy et al., 2020; Liu et al., 1). We summarize the success of Transformers into three main factors, which can also help resolve the aforementioned challenges in dynamic graph representation learning: (1) fully-coonnet self-attention: by modeling all pair- node relations, DGT can capture implicit edge connections,

---

Under review as a conference paper at ICLR 2022
thus become robust to graphs with noisy information such missing links; (2) positional encoding: by generalizing positional encoding to the graph domain using spatial-tempont encoding, we can inject both spatial and temporal graph evolutionary information as inductive biases into DGT to learn a graph's evolutionary patterns over time; (3) self-supervised pre-training: by optimizing two complementary pre-training tasks, DGT presents better performance on the downstream tasks.
Though powerful, training Transformers on large-scale graphs is non-trivial due to the quadratic complexity of the fully connected self-attention on the graph size (Zaheer et al., 2020; Wang et al., 2020). This issue is more severe on dynamic graphs as the computation cost grows with the number of time-steps in a dynamic graph (Pareja et al., 2020; Sankar al.. 2018). To make the training scalable and independent of both the graph size and the number of time-steps, we first propose a temporal-untee -union graph structure that aggregates graph information from multiple time-steps into unified meta-graph; we then develop a two-tower architecture with a novel target-context node sampling strategy to model subset of nodes with their contextual information. These approaches improve DGT's training efficiency and scalability from both the temporal and spatial perspectives.
To this end, we summarize our contributions as follows: (1) a two-tower Transformer-
method named DGT with spatial-temporal encoding that can capture implicit edge connections in addition to the input graph topology: (2) a temporal-ure -uioo graph data structure that efficiently summarizes the cnntial-temporal information of dynamic graphs and a novel target-context node sampling strategy for large-scale training: (3) two complementary pre-training tasks that can facilitate performing
downstream tasks and are proven beneficial using information theory; and (4) comprehensive evaluation on real-world datasets with ablation studies to validate the effectiveness of DGT.
PRELIMINARIES AND RELATED WORKS
In this section, we first define dynamic graphs, then review related literature on dynamic graph representation learning and Transformers on graphs.
Dynamic graph definition. The nodes and edges in a dynamic graph may appear and disappear over time. In this paper, we define a dynamic graph as a sequence of static graph snapshots with a where the (-th snapshot graph G. (V, & is an undirected graph
temporal order G 2 [Gi..... GT with a shared node set V of all time steps and an edge set &s. We also denote its adjacency matrix as A,. Our goal is to learn a latent representation of each node at each time-step f. such that the learned representation can be used for any specific downstream task such as link prediction or node classification. Please notice that the shared node set V is not static and will be updated when new snapshot graph arrives, which the same as Sankar et al. (2018); Pareja et al. (2020).
Dynamic graph representation learning. Previous dynamic graph representation learning methods usually extend static graph algorithms by further taking the temporal information into considera- tion. They can mainly be classified into three categories: (1) smoothness- basedd methods learn graph autoencoder to generate node embeddings on each graph snapshot and ensure the temporal smoothness of the node embeddings across consecutive time-steps. For example, DYGEM (Goyal et al., 2018) uses the learned embeddings from the previous time-step to initialize the embeddings in the next time-step. DYNAERNN applies RNN to smooth node embeddings at different time- steps; (2) Recuureen--bsed methods capture the temporal dependency using RNN. For example, GCRN (Seo et al., 2018) first computes node embeddings
each snapshot using GCN (Defferrard et al., 2016), then feeds the node embeddings into an RNN to learn their temporal dependency. EVOLVEGCN (Pareja al., 2020) uses RNN estimate the GCN weight parameters at different time-steps; (3) Aftention-based based methods use self-attention mechanism for both spatial and temporal message aggregation. For example, DYSAT (Sankar et al., 2018) propose to use the self-attention mechanism for temporal and spatial information aggregation. TGAT (Xu et al., 2020) encodes the temporal information into the node feature, then applies self-attention on the temporal augmented node features. However, smoothness-based methods heavily rely on the temporal smoothness and are inadequate when nodes exhibit vastly different evolutionary behaviors, recurrent- securren-bbased methods scale poorly when the number of time-steps increases due to the recurrent nature of RNN, attention- based methods only consider the self-attention on existing edges and are sensitive to noisy graphs. In contrast, DGT leverages Transformer to capture the spatial-temporal dependency between all nodes pairs, does not over-relying on the given graph structures, and is less sensitive to noisy edges.
Graph Transformers. Recently, several attempts have been made to leverage Transformer for
2

---

Under review as a conference paper at ICLR 2022
Temporal union graph
[Seetion 411
(a) Temporal Connection
Encoding generation (Section 4.3)
Pamparai Coneennon
Sporie
Distnner
WrightAneroge (N
Lnvor Projection
((22 #2
f2
Oge
(g) Spatial Distance
Massa
Emcoding generation (Section 4-3)
Aineor Projection
gintio
Ai
(5) Dynamic Graph Transformer (Section 4.4)
(4) Target node driven context pode sampling (Section
(E-1)
Query
Producr
Softmax
Product
PPN
H
Target coded
madee
Asp PesiPesi Vial
Hips
(f-1)
Value
ArclPasi Rigil
Ciriicas sodss
Siepping
(2-1)
Query
Product
Softmaax
Product
RPN
Aso (Mat: Vead ArcPPys: Voud
Task: Predict whether edge (1.5) in So
Figure I: Overview of using DGT for link prediction. Given snapshot graphs (91. 923 as input, (1) we first generate the temporal union graph with the considered max shortest path distance Dmax 5, and its associated (2) temporal connection encoding and (3) spatial distance encoding. Then, the encodings are mapped into ATC ASD for each node pairs (i,j) using a fully connected layer. To
predict whether an edge exists in future graph G3. we first (4) sample target nodes and context nodes, and then apply (5) DGT to encode target nodes and context nodes separately.
graph representation learning. For example, GRAPHORMER (Ying et al., 2021) and GRAPHTRANS- FORMER (Dwivedi & Bresson, 2020) use scaled dot-produd attention (Vaswani et al., 2017) for message aggregation and generalizes the idea of positional encoding graph domains. GRAPH- BERT (Zhang et al., 2020) first samples an egocentric network for each node, then order all nodes into a sequence based on node importance, and feed into the Transformer. However, GRAPHORMER is only feasible to small molecule graphs and cannot scale to large graphs due to the significant computation cost of full attention; aggregation, which makes it sensitive to noisy graphs; GRAPHBERT does not leverage the graph topology and can perform poorly when graph topology important. In contrast, DGT encodes the input graph structures as an inductive bias to guide the full-attention optimization, which balances the trade-off's between noisy input robustness and efficiently learning an underlying graph structure. A detailed comparison is deferred to Appendix D.
only considers the first-hop neighbor
METHOD
In this section, we first introduce the temporal union-graph (in Section 3.1) and our sampling strategy (in Section 3.2) that can reduce the overall complexity from the temporal and spatial perspectives respectively. Then, we introduce our spatial-temporal encoding technique (in Section 3.3), describe the two-tower transformer architecture design, and explain how to integrate the spatial-tempon encoding to DGT (in Section 3.4). Figure illustrates the overall DGT design.
3.1 TEMPORAL-UNIOX GRAPH GENERATION
One major challenge of applying Transformers on graph representation learning is its significant computation and memory overhead. In Transformers, the computation cost of self-attention is O(E)) d) and its memory cost is O[EE + |V] d). When using full attention, the computation graph is fully connected with [8| = 12/2. where the overall complexity is quadratic in the graph size. On dynamic graphs, this problem can be even more severe one naively extends the static graph algorithm to dynamic graph, e.g., first extracting the spatial information of each snapshot graph separately, then jointly reasoning the temporal information on all snapshot graphs (Sankar et al., 2018; Pareja et al., 2020). By doing the overall complexity grows linearly with the number of time-steps T, i.e., with O(D (Td) computation and 0(VVTT + [V[Td) memory cost. To reduce the the number of time-steps,
dependency of the overall complexity dynamic graphs G = .G..... GT) into a temporal-umion graph gunian (V, then employ DGT on the generated temporal-union graph, where E Unique (i,j) (i. &,, & [T]] is the set of
propose first aggregate
3

---

Under review as a conference paper at ICLR 2022
all possible unique edges in G. As result, the overall complexity of DGT does not grow with the number of time-steps. Details on how to leverage spatial-temporal encoding to recover the temporal information of edges are described in Section 3.3.
3.2 TARGET NODE DRIVEN CONTEXT NODE SAMPLING
Although the temporal-anion graph can alleviate the computation burden from the temporal dimension, due to the overall quadratic complexity of self-attention with respect to the input graph size, scaling the training of Transformer to real-world graphs is still non-trivial. Therefore, a properly designed sampling strategy that makes the overall complexity independent with graph sizes is necessary. Our goal is to design a sub-graph sampling strategy that ensures a fixed number of well-connected nodes and lower computational complexity. To this end, propose to first sample subset of nodes that we are interested in as targel nodes, then sample their common neighbors as context nodes.
Let target nodes Vi C V be the of nodes that are interested in and want compute its node representation. For example, for the link prediction task, Vig are the set of nodes that we aim to predict whether they are connected. Then, the context nodes Vex C (N(i) Vi E Vigt) are sampled as the common neighbors of the target nodes. Notice that since context nodes Vex are sampled as the common neighbors of the target nodes, they can provide local structure information for nodes in the target node set. Besides, since two different nodes in the target node set can be far apart with a disconnected neighborhood, the neighborhood of two nodes can provide an approximation of the global view of the full graph. During the sampling process, to control the randomness involved in the sampling process, Vas are chosen as the subset of nodes with the top- K joint Personalized PageRank (PPR) score (Andersen al., 2006) nodes in Vigt. where PPR score is node proximity measure that captures the importance of two nodes in the graph. More specifically, our joint PPR sampler proceeds as follows: First, we compute the approximated PPR vector π T() R for all node E Vigi. where the j-th element in π (1) can be interpreted as the probability of a random walk to start at node and end at node j. We then compute the approximated joint PPR vector A (Vigt= = Σiery T(i) E BA Finally, we select K context nodes where each node j E Vax has the top-K joint PPR score in A (Vig). In practice, we select the context node size the same as the target node size, i.e., K = D
3.3 SPATIAL-TEMPORAL ENCODING
Given the temporal canporal-union graph, our next step is to translate the ppatial-tempont information from snapshot graphs to the temporal-union graph Gunion. which can be recognized and leveraged by Transformers. Notice that most classical GNNs either over-rely on the given graph structure by only considering the first- or higher-order neighbors for feature aggregation (Ying et al., 2021). or directly learn graph adjacency without using the given graph structure (Devlin et al., 2019). On the one hand, over-relying on the graph structure makes the model fails to capture the inter-relation between nodes that are not connected in the labeled graph, and could be very sensitive to the noisy edges due to human- lamainla errors. On the other hand, completely ignoring the graph structure makes the optimization problem challenging because the model has iteratively learn model parameters and estimate the graph structure. To avoid the above two extremes, we present two simple but effective designs of encodings, i.e., temporal connection encoding and spatial distance encoding, and provide details on how to integrate them into DGT.
Temporal connection encoding. Temporal connection (TC) encoding designed inform DGT if an edge (i,j) exists in the f-th snapshot graph. We denote Е = TC 1, cz e E 2T xd as the temporal connection encoding lookup-table where represents the hidden dimension size, which is indexed by function jit. indicating whether an edge (i.j) exists at time-step t. More specifically, we have (i) = 2/ if (i,j) E Gr. (i, 1) = 21 i (i.j) & G. and use this value as index to extract the corresponding temporal connection embedding from the look-up table for next-step processing. Note that during pre-training or the training on first few time-steps, we need to mask-out certain time-steps to avoid leaking information related to the predicted items (c.g., the temporal reconstruction task in Section, 4.1.. In these cases, we set (f(i, j. t') = Ø where 1! denotes the time-step we mask-out, and skip the embedding extraction time f'.
Spatial distance encoding. Spatial distance (SD) encoding is designed to provide DGT a global view of the graph structure. The success of Transformer is largely attributed to its global receptive
4

---

Under review as a conference paper at ICLR 2022
field due its full attention, i.e. each token in the sequence can attend independently to other tokens and process its representations. Computing full attention requires the model to explicitly capturing the positions dependency between tokens, which can be achieved by either assigning each position an absolute positional encoding or encode the relative distance using relative positional encoding. However, for graphs, the design of unique node positions is not mandatary because graph is not changed by the permutation of its nodes. To encode the global structural information of a graph in the model, inspired by (Ying et al., 2021), we adopt a spatial distance encoding that measures the relative spatial relationship between any two nodes in the graph, which is a generalization of the classical Transformer's positional encoding to the graph domain. Let Dmax be the maximum shortest path distance (SPD) we considered, where Dmax is can be smaller than the graph diameter. More specifically, given any node and node j. we define ((i,)) min(SPD(i, j). D max) as the SPD between the two nodes if SPD(i, < mmax and otherwise as Dmax- Let ESD = [ei .e..,..., ...., @Dmas E II Pmax xd as the spatial distance lookup-table SD which is indexed by the (ii,j), where ((i, j) is used to select the spatial distance encoding (((.))
pperrparreeter that
that provides the spatial distance information of two nodes.
Integrate spatial-temporal encoding. We integrate temporal connection encoding and spatial distance encoding by projecting them bias term in the self-attention module. Specifically, to integrate the spatial-temporal encoding of node pair (i.j] to DGT, we first gather all its associated temporal connection encodings different time-stpps as {c (Ciijjj)) 1 Then, we apply weight average on all encodings over the temporal axis and projected the temporal averaged encoding as E R. where the aggregation weight is
a scalar by A/S = Linear( Weighttverage((eel.. Te ((.,) learned during training. Similarly, to integrate the spatial distance encoding, we project the spatial distance encoding of node pair (i.j) as a scalar by A. Linear(e )(i.))) E R. Then, A!G and A are used as the bias term to the self-attention, which we describe in detail in Section 3.4.
3.4 GRAPHI TRANSFORMER ARCHITECTURE
As shown in Figure 1, each layer in DGT consists of two towers (i.e., the target node tower and the context node tower) to encode the target nodes and the context nodes separately. The same set of parameters are shared between two towers. The two-tower structure is motivated by the fact that nodes within each group are sampled independently but there exist neighborhood relationships between inter- inter-group nodes. Only attending inter-group nodes help DGT better capture this context information without fusing representations from irrelevant nodes. The details are as follows:
First, we compute the self-attentions that are used to aggregate information from target nodes to context nodes (denote as "ctx") and from context nodes to target nodes (denote as "tgt"). ). Let define H(O) etx
E IR Vas xd as the ε-th layer output of the context-node tower and H(() E IR Vigl xd as the /-th layer output of the target-node tower. Then, the εth layer self-attention is computed as (MA(HH("))Wer (IN(H lgt
(LN(H (f-1) w!()) (I () T
(f-1) w (LN(H (C-1) W
A ctx
(8)
Vd
Vd Q K are weight matrices.
where LN(H) (H) stands for applying layer normalization on H and ((() w
Then, we integrate ppatial-temporal encoding as bias term to self-attention as follows
ctx p(() = - + Arc(Vexs Viel= + Asp Vens Vigil. P = All + Arc Vaal + AsD Digs Venl,
where AAc Vel, ASD [Ai Val denote the the matrix form of the projected temporal connection
and spatial distance self-attention bias with row indexed by VA and columns indexed by VB.
After that, we use the normalized (ff) and p(()
igi to propagate information between two towers, i.e.,
_! = Softmax (P (2)
ctx (H (L-1) (( H (1-1) z!d) Softmax (P ( ( +H((-1)
Finally, residual connected ferd-forward network is applied to the aggregated message to produce the final output
FFN(LN
igi FFN(LN(Z Lgg
igt
where FFN(-) denotes the multi-layer feed-forward network. The final layer output of the target node tower H!
ggt will be used to compute the loss defined in Section 4.
(L)
'Given a matrix A E Rm the element at the i-th row and j-th column is denoted as Ar,j, the submatrix formed from row Ipo {a....., } and columns Taa (bi,...,by b.) is denoted as A [Tao Tcal--
5

---

Under review as a conference paper at ICLR 2022
Feram (0)
Vist
Turget nodes
DyGrapi/Tannsooruu
11
Chekkd zode
Content mode V. receeneeeeeeee
Larget nodes
Eviune (0)
Surpligg
DyüraphTrnnsfrmme
g
Figure 2: Overview of the pre-training. Given snapshot graphs { 92 as input, we first generate the temporal union graph. Then, we sample the target node Vgu and two different set of context nodes Vax. Vexx After that, we apply DGT on (Vig,. Vea and {Vigt+ Vea.] to output H and H To this end, we optimize Lvee ()) by maximizing the similarity between (L) and H and optimize frecom (+) by recovering snapshot graphs using H
1igh,
ggt
DYNAMIC GRAPH TRANSFORMER LEARNING
Transformer usually requires a significant amount of supervised data to guarantee their generalization ability unseen data. However, existing dynamic graph datasets relatively small and may not be sufficient to train powerful Transformer. To overcome this challenge, we propose to first pre-train DGT with complementary self-supervised objective functions (in Section 4.1). Then, we fine-tine DGT using the supervised objective function (in Section 4.2). Notice that the same set of snapshot graphs but different objective functions are used for pre-training and fine-tuning, Finally, via an nnformation-theoree analysis, we show that the representation can have a better generalization ability on downstream tasks by optimizing our pre-training losses (in Section 4.3).
4.1 PRE-TRAINING
We introduce a temporal reconstruction loss Leccnn (+) and a multi-view contrastive loss Lview as our self-supervised object functions. Then, our overall pre-taining loss is defined as Cpre-trinn ( frecom ( + (O), where y is byper-parameter that balances the importance of two pre-taining tasks as illustrated in Figure 2.
Temporal reconstruction loss. To ensure that the spatial-tempont encoding is effective and can inform DGT the temporal dependency between multiple snapshot graphs, we introduce temporal reconstruction loss as our first pre-training objective. Our goal is to reconstruct the I-th graph snapshot 9,'s 's structure using all but except the 1-th graph snapshot (i.e., G 9.). Let H (t) denote the target- node tower's 's final layer output computed on Ge. To decode the graph structure of graph snapshot G. we use fully connected layer the temporal structure decoder that takes H (t) as input and output E({) Linear(H.g. ig (t)) RR (Va x with (t) E Rd denotes the i-th row of E((). Then, the temporal reconstruction loss is defined as Lreemn ()) = Et= LinkPredLoss([ (e)()) Vigs Ex), where a (.) is Sigmoid function and
LinkPredLoss (x) S,E)
( lx x,)) - Σ log(1 - o(x x)))) (I)
LJES
(K,)EE
(FJ)EE
Recall that Vax is constructed by deterministically selecting the common neighbors of Vigi with the top-K PPR score. Then, we introduce Vax as the subset of the common neighbors of Vigi randomly sampled with sampling probability of each node proportional to its PPR score. Since a different set of context nodes are provided for the same set of target nodes, OVy. Van} provides an alternative view of (Vigt Vax) when computing the representation for nodes in Vigi- Notice that although the provided context nodes are different, since they have the same target nodes, it is natural to expect the calculated representation have high similarity. denote H and H! as the final layer model output that are computed on {Vig,, Van and (Vigi, Vex) To this end, we introduce our second self self-supervised objective function Lview (e)
Multi-view contrastive loss.
[|A ig SStopGrad H (L) Il + ||StopGrad (5) ggt Hi Iiz. where StopGrad denotes stop gradient. gt
Note that optimizing Cview ) alone without stopping gradient results in a degenerated solution (Chen
& He, 2021; Tian et al., 2021).

---

Under review as a conference paper at ICLR 2022
4.2 FINE-TUNING
To apply the pre-trained model for downstream tasks, we choose to finetune the pre-trained model with downstream task objective functions. Here, we take link prediction as an example, Our goal is to predict the existence of link at time T + using information up to time T. Let Hig ([9, ==1) denote the final layer output of DGT using snapshot graphs (9) Jj=1- Then, the link prediction loss defined as LLinkPred (+) = > LinkPredLoss( H H
lgt (19))}=1) Vigta E141), where Lee
is defined in Eq.
4.3 ON THE IMPORTANCE OF PRE-TRAINING FROM INFORMATION THEORY PERSPECTIVE
In this section, we show that our pre- vre-training objectives can improve the generalization error under mild assumptions and results in a better performance on downstream tasks. Let X denote the input random variable, S as the self-supervised signal (also known as a different view of input X), and Zx = f(x), 7s
S(S) as the representations that are generated by a deterministic mapping function f. In our setting, we have the sampled sub-graph of temporal-union graph Gunion induced by node (Vig,, Vax] as input X. the sampled subgraph of Gunion induced by node Vigh, Varx } as self-supervised signal S, and DGT f that computes the representation of X, S by Zx = f(X), ; Zs- = f(S). Besides, we introduce the task-relevant information as Y, which refers to the information that is required for downstream tasks. For example, when the downstream task is link prediction, Y can be the ground truth graph structure about which we want to reason. Notice that in practice have access Y during pre-training and it is only introduced as the notation for analysis. Furthermore, let H ((A) denote entropy. ((A) B) denote conditional entropy. 7 [(A; B) denote mutual information, and I (AA; BIC) denote conditional mutual information. More details and preliminaries on information theory are deferred to Appendix B.
In the following, we study the generalization error of the learned representation Zx under the binary classification setting. We choose Bayes enror rate (i.e., the lowest possible test error rate a binary classifier can achieve) as our evaluation metric, which can be formally defined as P. 1 - [mmax, P(Y = y| Zx Before proceeding to our result, we make the following assumption on input X, self-supervised signal S, and task task-relevant information Y.
Assumption 1. We assume the task-relevant information is shared between the inpul random variable X, self-supervised signal S. i.e., we have I(S; = and I( ((): = O.
We argue the above assumption mild because input X and self-supervised signal S are two different views of the data, therefore they are expected to contain task-relevant information Y. In Proposition 1, we make connections between the Bayes error rate and pre- pre-training training losses, which explains why the proposed pre-training losses are helpful for downstream tasks. We defer the proofs to Appendix B.
Proposition We can upper bound Bayes error rate by Pa S - exp(-H(Y) ( + I(Zx; X)
([Zx:X|Y)) and reduce the upper bound of P. by (1) maximizing the mutual information I(Zx; X) between the learned representation Zx and input X, which can be achieved by minimizing temporal reconstruction loss Crcom(() (+), and (2) minimizing the task- task-irrelevant information between the learned representation Zx and input X, which can be achieved by minimizing our multi-view loss Lview (D).
The Proposition suggests that if can create different views S of our input data X in way such that both X and S contain the task-relevant information Y. then by jointly optimizing our two pre-training losses can result in the representation Zx with lower Bayes error rate P.. Our analysis is based on the information theory framework developed in (Tsai et al., 2020), in which they show that using contrastive loss between Zx and S (i.e., maximizing [(2x; S)), predicting S from Zx Z )), and predicting Zx from S (i.c., minimizing / (Zx\S)) can result in a
(i.e., minimizing H ZS) smaller Bayes error rate P
EXPERIMENTS
We evaluate DGT using dynamic graph link prediction, which has been widely used in (Sankar et al., 2018; Goyal et al., 2018) to compare its performance with variety of static and dynamic graph representation learning baselines. Besides, DGT can also be applied to other downstream tasks such as node classification. We defer node classification results to Appendix A.3.
7

---

Under review as a conference paper at ICLR 2022
Table I: Comparing DGT with baselines using Micro- and Macro-AUC on real-world datasets.
Method
Metric
Enron
RDS
UCI
Yelp
ML.II0M
Micro-UUC
82.42 1: 2.03
81.10 0.87
81.41 1 0.60
68.93
0.33
90.50 0.83
NODE2VEC
Macro-AUC
81.35 + 2.93
82.85 + 0.86
81.39 + 0.76
67.38
+ 0.49
89.48 + 0.62
GRAPISAGE
Micro-AUC
82.39 1 3.01
85.49 = 0.96
79.85 0155::20:
62.36
1.01
86.31 = 0.97
Macro-AUC
83.41
2.91
86.61
0.89
2.00
58.36
= 0.91
90.23 0.90
DYNAERNN
Micro-AUe
74.00
1.24
80.56
0.77
79.29 1.90
71.54
0.83
87.01 0.88
Macro-AUC
74.36 + 1.35
80.16 + 0.91
83.81 + 1.25
72.29
+ 0.58
89.04 = 0.67
DYNGEM
Micro-UCC
66.16 4 0.71
79:29 = 1.01
76.36
0.83
09:13
= 1.09
79.80 = 0.58
Macro-AUC
68.46
1.14
81.94
1.97
78.22
0.99
69.93
0.78
84.86 0.49
DYSAT
Micro-AUC
83.81 =: 1.55
83,89 = 0.392
83.10 0.99
69.00
= 0.22
58.91 = 0.87
Macto-AUC
83.73 1.61
83.60
0.68
86.32 +: L.46
69.42
0.25
90.63 0.91
EVOLVEGON
Micro-AUIC:
73.83 + 1.25
85.35
0.87
85.81 + 0.50
68.99 0.67
92.79 + 0.21
Macro-AUC
75.77 4: 1.57
86.53 + 0.76
84.18 0.72
69.41
0.26
93.45 = 0.19
DGT
MiCr-AUC
87.32 1: 0.87
58.77 0.50
87.91
0.32
73.39
0.21
96.30 : 0.36
Macro-AUC
87.82 + 0.89
89.77 + 0.46
88.49 + 0.43
74.31 + 0.23
96.16 + 0.22
5.1 EXPERIMENT SETUP
Datasets. We select five real-world datasets of various sizes and types in our experiments. The detailed data statistics can be accessed Table 11 in Appendix C.2. Graph snapshots are created by splitting the data using suitable time windows such that each snapshot has an equitable number of interactions. In each snapshot, the edge weights are determined by the number of interactions.
Link prediction task. To compare the performance of DGT with baselines, we follow the evaluation strategy in (Goyal et al., 2018; Zhou al., 2018; Sankar et al., 2018) by training a logistic regression classifier taking two node embeddings as input for dynamic graph link prediction. Specifically, we learn the dynamic node representations on snapshot graphs {9.................... G and evaluate DGT by predicting links at GT+1. For evaluation, we consider all links in Gr-1 as positive examples and an equal number of sampled unconnected node pairs as negative examples. We split 20% of the edge examples for training the classifier, 20% of examples for hyper-pan seper-parameterss tuning, and the rest 60% of examples for model performance evaluation following the practice of existing studies (c.g., (Sankar et al., 2018) 8)). We evaluate the link prediction performance using Micro- and Macro-AUC scores, where the Micro-AUC is calculated across the link instances from all the time-steps while the Macro- AUC is computed by averaging the AUC at each time-step. During inference, all nodes in the testing set (from 60% edge samples in GT+I) are selected as the target nodes. To scale the inference of the testing sets of any sizes, we compute the full attention by first splitting all self-attentions into multiple chunks then iteratively compute the self-attention in each chunk (as shown in Figure 7). Since only a fixed number of self-attention computed at each iteration, we significantly reduce DGT 's inference memory consumption. We also repeat all experiments three times with different random seeds.
Baselines. We compare with several state-of of-te-of-thearr art methods as baselines including both static and dynamic graph learning algorithms. For static graph learning algorithms, we compare against NODE2 (Grover & Leskovee, 2016) and GRAPHSAGE the comparison fair, we feed these static graph algorithms the same temporal-union graph used in DGT rather than any single graph snapshots. For dynamic graph lcarning algorithms, we compare against DYNAERNN (Goyal et al., 2020), DYNGEM (Goyal et al., 2018), DYSAT (Sankar et al., 2018), and EvolveGCN (Pareja et al., 2020). We use the official implementations for all baselines and select the best syper-parameters for both baselines and DGT. Notice that we only compare with dynamic graph algorithms that takes a set of temporal ordered snapshot graph as input, and leave the study on other dynamic graph structure (e.g., continuous time-step algorithms (Xu al., 2020; Rossi et al., 2020)) as a future direction. More details on experiment configurations are deferred to Appendix C and more results (Figure 4, Table 2 and 3) are deferred to Appendix A.I.
(Hamilton et al., 2017). To make
5.2 EXPERIMENT RESULTS
Table indicates the state-of-the-at performance of our approach on link prediction tasks, where DGT achieves consistent 1% ~ 3% Macro-AUC gain on all datasets. Besides, DGT is more stable when using different random seeds observed from a smaller standard deviation of the AUC score. Furthermore, to better understand the behaviors of different methods from a finer granularity, we compare the model performance at each time-step in Figure 4 and observe that the performance of DGT is relatively more stable than other methods over time. Besides, we additionally report the results of dynamic link prediction evaluated only unseen links at each time-step. Here, we define unseen links as the ones that first appear at the prediction time-step but are not in the previous graph snapshots. From Table 2, we find that although all methods achieve lower AUC score, which may
8

---

Under review as a conference paper at ICLR 2022
Stege
Talp
Macre-ADe
Macr-AUC
MacToADC
Macre-Mtic
With proitram 0.891
With truce (58 65 0.831
With (1433
2.221
Negs
Thex Shipe
Tian
Thee
Figure 3: Comparison of the Micro- and Macro-AUC score of DGT with and without pre-training.
be due to the new link prediction is more challenging, DGT still achieves a consistent 1% ~ 3% Macro-AUC gain over baselines. Moreover, we compare the training time and memory consumption with several baselines in Table 3 and shows that DGT maintains a good scalability.
5.3 ABLATION STUDIES
We conduct ablation studies to further understand DGT and present the details in Appendix A.2. The effectiveness of pre-training. We compare the performance of DGT with and without pre- training. As shown in Figure 3, DGT 's performance is significantly improved if we first pre-train it with the self-supervised loss with a fine-tuning on downstream tasks. When comparing the AUC scores at each time-step, we observe that the DGT with no pre-training has relatively lower performance but a larger variance. This may be due the vast number of training parameters in DGT, which potentially requires more data to be trained well. The self-supervised pre-training alleviate this challenge by utilizing additional unlabeled input data.
Comparing two-tower to single-tower architecture. In Table 4, we compare the performance of DGT with single- and two-tower design where a single-tower means full-attention of over all pairs of target and context nodes. We observe that the two-tower DGT has consistent performance gain (0.5% Micro- and Macro-AUC) over the single-tower on Yelp and ML-10M. This may be due to that the nodes within the target or context node set are sampled independently while inter-group nodes are likely to be connected. Only attending inter-group nodes helps DGT better capturing these contextual information without fusing representations from irrelevant nodes.
Comparing K Khhop attention with full attention. To better understand full-attention, we compare it with sparson and ions such as 1-hop and 3-hop attention. These variants evaluated based on the single-tower DGT to include all node pairs into consideration. Table 5 shows the results where we observe that the full attention presents a consistent performance gain around 1% 3% over the other two variants. This demonstrates the benefits of full-attention when modeling implicit edge connections in graphs with larger receptive fields comparing its K-hop counterparts.
The effectiveness of independently removing two encodings to validate the effectiveness of spatial-temporal encoding. We observe that even without any encoding (i.c., ignoring the spatoal-temporal graph topologies), due to full attention, DGT still very competitive comparing with the state-of-the thether-rttt baselines in Table 1. However, we also observe a 0.6% ~ 4.6% performance gain when adding the spatial connection and temporal distance encoding, which empirically shows their effectiveness.
encoding. In Table 6, we conduct an ablation study by
The effectiveness of stacking more layers. When stacking more layers, traditional GNNs usually suffer from the over-smoothing (Zhao & Akoglu, 2020; Yan et al., 2021) and result in degenerated performance. We study the effect of applying more DGT layers and show results in Table 7. In contrast to previous studies, DGT has a relatively stable performance and does not suffer much from performance degradation when the number of layers increases. This is potentially due to that DGT only requires a shallow architecture since each individual layer is capable of modeling longer- range dependencies due to full attention. Besides, the self- attentonnn mechanism automatically attend importance neighbors, therefore alleviate the over-smoothing and bottleneck effect.
6 CONCLUSION
In this paper, we introduce DGT for dynamic graph representation learning, which can efficiently leverage the graph topology and capture implicit edge connections. To further improve the general- ization ability, two complementary pre- pre-training tasks are introduced. To handle large-scale dynamic graphs, temporal-union graph structure and a target-context node sampling strategy are designed for an efficient and scalable training. Extensive experiments on real-world dynamic graphs show that DGT presents significant performance gains over several state-of-the-e basclines. Potential future directions include exploring GNNs on continuous dynamic graphs and studying its expressive power.

---

Under review as a conference paper at ICLR 2022
Reproducibility Statement. We summarize the hardware specification and environment used in experiments in Appendix C.I, details on all datasets in Appendix C.2, details on baseline hyper- parameters tuning in Appendix C.3, details on DGT proof of theory in Appendix B. We plan to release our code afterwards or being requested by the reviewers during the review phase.
in Appendix C.4, and the
REFERENCES
Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using pagerank vectors. In Foundations of Computer Science, 2006.
Rianne van den Berg, Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. In International Conference on Knowledge Discovery & Data Mining, 2017.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, 2020.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In Conference on Advances in Neural Information Processing Systems, 2021.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. 2006.
Zhiyong Cui, Kristian Henrickson, Ruimin Ke, and Yinhai Wang. Traffic graph convolutional recurrent neural network: deep learning framework for network-scale traffic learning and forecasting. IEEE Transactions on Intelligent Transportation Systems, 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, 2016.
Jacob Devlin, Ming-Weeeeee Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2019.
Kien Do, Truyen Tran, and Svetha Venkatesh. Graph transformation policy network for chemical reaction prediction. In International Conference on Knowledge Discovery & Data Mining, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.1 1999. 2020.
David Duvenaud, Dougal Maclaurin, Jorge Aguilera-pparraguire,, Rafael Gómez-Bombarelli, Tim- othy Hirzel, Alán Aspuru-Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems, 2015.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699 2020.
Meir Feder and Neri Merhav. Relations between entropy and error probability. IEEE Transactions on Information theory, 40, 1994.
Palash Goyal, Nitin Kamra, Xinran He, and Yan Liu. Dyngem: Deep embedding method for dynamic graphs. CoRR, 2018.
Palash Goyal, Sujit Rokka Chhetri, and Arquimedes Canedo. dyngraph2vec: Capturing network dynamics using dynamic graph representation learning. Knowledge- Based Systems, 187, 2020.
10

---

Under review as a conference paper at ICLR 2022
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In International Conference on Knowledge Discovery and Data Mining, 2016.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun, Heterogeneous graph transformer. In WWW 20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In International Conference on Knowledge Discovery & Data Mining, 2019.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. arXiv preprint arXiv:2103. 2021.
Kevin P. Murphy. Probabilistic Machine Learning: An introduction. 2022.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao Schardl, and Charles Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. In Conference on Artificial Intelligence, volume 34, 2020.
Afshin Rahimi, Trevor Cohn, and Timothy Baldwin. Semi-supervised user geolocation via graph convolutional networks. In Proceedings of the Association for Computational Linguistics, 2018.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint vrXiv:2006.10637 2020.
Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dynamic graph representation learning via self-attention networks. arXiv preprint arXiv: 1812. 2018.
Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. In International Conference on Neural Information Processing, 2018.
Yuandong Tian, Xinlei Chen, and Surya Ganguli. Understanding self-supervised learning dynamics without contrastive pairs, arXiv preprint 10X.::2022.06800, 2021.
Yao-Hung Hubert Tsai, Yue Wu, Ruslan Salakhutdinov, and Louis-Philippe Morency. Self-supervised learning from multi-view perspective. arXiv preprint arXhv:2006.05576, 2020.
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, 2017.
Hongwei Wang, Fuzheng Zhang, Mengdi Zhang, Jure Leskovec, Miao Zhao, Wenjie Li, and Zhongyuan Wang. Knowledge-aware graph neural networks with label smoothness regular- ization for recommender systems. In International Conference on Knowledge Discovery & Data Mining, 2019a.
Sinong Wang, Belinda 7 LIi, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.044 047668 2020.
Xiang Wang, Xiangnan He, Yixin Cao, Meng Liu, and Tat-Seng Chua. KGAT: knowledge graph attention network for recommendation. In International Conference on Knowledge Discovery & Data Mining, 2019b.
Da Xu, Chuanwei Ruan, Evren Körpeoglu, Sushant Kumar, and Kannan Achan. Inductive repre- sentation learning on temporal graphs. International Conference on Learning Representations, 2020.
11

---

Under review as a conference paper at ICLR 2022
Yujum Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.06442, 2021.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tan Liu. Do transformers really perform bad for graph representation? arXiv preprint 2xXi:22006.05334, 2021.
Rex Ying. Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In International Conference on Knowledge Discovery Data Mining, 2018.
Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J. Kim. Graph transformer networks. In Advances in Neural Information Processing Systems, 2019.
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang. Li Yang, et al. Big bird: Transformers for longer sequences. In Advances Neural Information Processing Systems, 2020.
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.05140, 2020.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International
Conference on Learning Representations, 2020.
Dawei Zhou, Lecheng Zheng, Jiawei Han, and Jingrui He. A data-driven graph generative model for temporal interaction networks. In International Conference on Knowledge Discovery & Data Mining, 2020.
L. Zhou, Y. Yang, X. Ren, F. Wu, and Y. Zhuang. Dynamic Network Embedding by Modelling Triadic Closure Process. Conference on Artificial Intelligence, 2018
12

---

Under review as a conference paper at ICLR 2022
Appendix
Table of Contents
A More experiment results
14
A.1 Link prediction results
14
A.2 Ablation study results.
15
A.3 Node classification results
17
Results on noisy dataset
A.5 Comparison with continuous graph learning algorithms
................................
B Pre-training reduce the irreducible error
18
B.1 Preliminary on information theory
18
B.2 Proof of Proposition
20
Experiment configuration
21
C.I Hardware specification and environment
21
C.2 Details datasets
................................
21
C33 Details baseline hypter parameters tuning
................................
22
C.4 Additional details on experiment configuration
23
D Comparison of different graph Transformer
23
D.1 Positional encoding types
24
Graph Transformer with other applications
24
13

---

Under review as a conference paper at ICLR 2022
A MORE EXPERIMENT RESULTS
A. LINK PREDICTION RESULTS
In this section, we provide the remained figures and tables in Section 5.
Comparison of AUC score at different time steps. In Figure 4, we compare the AUC score of DGT with baselines on Enron, UCI, Yelp, and ML-10M dataset. We can observe that DGT can consistently outperform baselines on Enron and ML-10M dataset at all time steps, but has a relatively lower AUC score certain time steps on the UCI and Yelp dataset. Besides, the performance of DGT is relatively more stable than baselines on different time steps.
L'Cll
0.
RXpAATION (M 1.200
DSRATTRON (XL (.55)
USSAA 73 1,40
AUC can
DSSAT 1B TAG)
048
DGT 297.82
DCT (5647
cop
Thoe Stags
Tioe Stogs
Yelp
0.79
Nacro AUC
0.3
Macro AUC
PyS07 rea 42 0.20
BysASno0 172 1.500
ADDC 300
PSRAT (39 no 6.10
TyxAE1oN 189
ExiT
bxiT
Timse Shops
Timse Shope
Figure 4: Comparison of DGT with baselines across multiple time steps, where the Macro-AUC
score is reported in the box next to the curves.
Comparision of AUC score on new link prediction task. In Table 2, we report dynamic link prediction result evaluated only on the new links at each time step, where a link that appears at the current snapshot but not in the previous snapshot is considered as a new link. This experiment can provide an in-depth analysis of the capabilities of different methods in predicting unseen links. As shown in Table 2, all methods achieve a lower AUC score, which is expected because new link prediction is more challenging. However, DGT still achieves consistent gains of 3% Macro-AUC over baselines, thus illustrate its effectiveness in accurately temporal context for new link prediction.
Table 2: Comparison of Micro- and Macro-AUC on real-world datasets restricted to new edges.
Method
Metric
Enron
RDS
Yelp
ML-1OM
NODE2VEC
Micro-AUC
76.45 1.15511.9 1.93
75.62 1.42
75.31 = 0.83
68.83 = 0.29
88.92
Macro-AUC
76.01 + 2.39
76.25 + 0.85
75.82 = 0.96
68.00 + 0.51
88.01 + 0.50
Micro-AUC
74.36 + 2.88
80.21 + 0.87
76.56 + 1.91
61.97 + 1.00
85.18 + 0.89
GRAPHSAGE
Macro-AUC
74.42 + 2.64
79.99 +: 0.78
75.94
1.88
58.49 + 0.89
89.31 0.93
Miem-AUC
61.81 + 1.89
68.43 + 1.13
77.39
2.10
70.82 + 0.93
86.89 + 0.75
DYNAERNN
Macro-AUC
62.62 1 1.91
68.18 1 1.23
81.82
1.71
71.56 1. 0.77
89.45 1 0.53
Micro-AUC
59.42 + 1.42
72.43 = 1.62
74.72
= 0.73
09.23 + 1.76
77.18 + 1.96
DYNGEM
Macro-AUC
61.61 +: 1.91
74.49 1: 2.21
76.34 - 0.78
70.67 + 1.32
82.62 +: 0.49
Miem-AUCC
75.78 + 1.89
76.28 + 1.34
81.18
1.09
09.12 + 0.21
88.21 0.64
DYSAT
MaCro-AUC
76.92 + 1.81
76.87 = 1.21
83.43 = 1.67
69.20 + 0.20
88.98 + 0.87
EVOLVEGCN
Micto-UUC
67.82 1 1.71
78.36 1 0.91
81.09
0.73
68.73 1 0.64
90.91 1 0.32
Macro-AUC
69.39 +: 1.89
79.18 1 1.01
82.18
0.76
68.63 1 0.30
91.45 1 0.29
Mien-AlIC
81.99 0.90
82.78
+ 0.56
85.78
0.99
73.32
1 0.22
93.01
0.23
DGT
Macro-AUC
81.32 - 0.89
82.89 + 0.52
86.21 + 0.56
73.88 + 0.22
93.56 0.21
14

---

Under review as a conference paper at ICLR 2022
Computation time and memory consumption. In Table compare the memory consumption and epoch time on the last time step of ML-10M and Yelp dataset. We chose the last time step of these two datasets because its graph size is relatively larger than others, which accurate time and memory estimation. The memory consumption is record by nvi wiidia a a-smi and the time is recorded by function t time... time () During pre-training, DGT samples 256 context node and 256 context node at each iteration. During fine-tuning, DGT first 256 positive links (links in the graph) and sample 2, 560 negative links (node pairs that do not exist in the graph), then treat all nodes in the sampled node pairs at target nodes and sample the same amount of context nodes. Notice that although the same sampling size hyper-pane parr-parreeter used, since the graph size and the graph density are different, the actual memory consumption and time are also different. For example, since the Yelp dataset has more edges with more associated nodes for evaluation than ML-10M, the memory consumption and time are required on Yelp than on ML-10M dataset.
provide more
Table 3: Comparison of the epoch time and memory consumption of DGT with baseline methods on the last time step of ML-10M and Yelp dataset using the neural architecture configuration summarized in Section C.4.
Dataset
Method
Memory consumption
Epoch time
Total time
DYSAT
9.2 GB
97.2 Sec
4276.8 See (45 epochs)
EVOLVEGCN
13.6 GB
6.9 Sec
821.1 Sec (120 epochs)
ML-10M
DGT (Pre-training)
6,5 GB
38.9 Sec
986.5 See (89 epochs)
DGT (Fine-tuning)
10.1 GB
2.98 Sec
62.2 Sec (22 epochs)
DYSAT
5.4 GB
29.4 Sec
4706.4 Sec (160 epochs)
EVOLVEGCN
7.5 GB
19.14 Sec
1091.2 Sec (57 epochs)
Yelp
DGT (Pre-training)
21.3 GB
11.8 Sec
413.5 Sec (34 epochs)
DGT (Fine-tuning)
21.3 GB
21.41 See
521.6 Sec (23 epochs)
A.2 ABLATION STUDY RESULTS.
In this section, we provide missing the tables in Section 5.3, where discussion on the results are provided in Section 5.3.
Compare two-tower to single-tower architecture. Table 4, we compare the Micro-AUC score and Macro-AUC score of DGT with one-tower" and two-tower structure UCI, Yelp, and ML-10M datasets.
Table 4: Comparison of the Micro- and Macro-AUC of DGT using single-tower and two-tower model architecture on the real-world datasets.
Method Metrie
UCI
Yelp
MI.100
Micro-AUC
87.86 + 0.60
72.95
0.20
94.80 0.81
Single-tower
Macro-AUC
88.27 + 0.68
73.81
+ 0.21
95.49 14.99+0.55
AuC
87.91 + 0.32
73.39
0.21
95.30
0.36
Two-tower
Macro-AUC
88.49 + 0.43
74.31 + 0.23
96.16 + 0.22
2 The node representation ( in the single-tower DGT is computed
( (FN(LN(Z( (
(IN((H
W (LL((H
(4)
Softmax
Arc Aso LN
+H
(H(1
dd
(2)
15

---

Under review as a conference paper at ICLR 2022
Compare K Khoop attention with full attention. In Table 4, we compare the performance of single tower DGT using aull-attention", "single-tower DGT using 1-hop attention", and "single-tower DGT using 3-hop attention" the UCI, Yelp, and ML-10M dataset.
Table 5: Comparison of the Micro- and Macro-AUC of full attention and K Khhop attention using the single-tower architecture on the real-world datasets.
Method
Metrie
UCI
Yelp
MI.-10M
Micro-AUC
87.86 = 0.60
72.95
0.20
94.80
0.81
Full attention
Macro-AUC
88.27 + 0.68
73.81
0.21
95.49
0.57
Micro-AUC
84.62 + 0.31
71.33 0.43
91.88 0.73
1-hop neighbor
Macro-AUC
85.10
71.45
0.45
0.44
MiC
87.01 + 0.89
71.19 0.22
91.83 + 0.92
3-hop neighbor
Macro-AUC
87.48 + 0.88
72.31
0.22
92.33 0.82
The effectiveness of spatial-temporal encoding. In Table 6, we validate the effectiveness of spatial-temporal encoding by independently removing the temporal edge coding and spatial distance encoding.
Table 6: Comparison of the Micro- and Macro-AUC of with and without spatial-temporal encoding the real-world datasets. Method
Metric
UCI
Yelp
ML-10M
Micro-AUC
87.91 0.32
73.39 + 0.21
95.30 + 0.36
With both encoding
Macro-AUC
88.49 + 0.43
74.31 + 0.23
96.16 0.22
Micro-AUC
83.27 +.29
72.82 = 0.37
91.1 0.43
Without any encoding
Macro-AUC
83.87 0.47
73.80 0.38
92.59 0.35
Micro-AUC
84.78
73.36 + 0.26
94.51
Only temporal connective encoding
Macro-AUC
84.60 0.42
74.31 + 0.25
95.43 + 0.29
Micro-AUC
87.01 0.46
72.98 + 0.32
92.34 0.40
Only spatial distance encoding
Macro-AUC
87.99 0.47
73.90 + 0.36
93.13 + 0.33
The effect of the number of layers. In Table 7, we compare the Micro-AUC score and Macro-AUC score of DGT with different number of layers the UCI, Yelp, and ML-10M datasets.
Table Comparison of the Micro- and Macro-AUC score of DGT with different number of layers on the real-world datasets.
Method
Metric
UCI
Yelp
ML-10M
Micro-AUC
87.80 i 0.43
74.30 1 0.21
94.99 = 0.21
layers
Macro-AUC
88.31 + 0.53
74.29 + 0.23
96.08 0.15
Micro-AUC
87.42
73.39 + 0.21
95.30 0.36
layers
Micro-AUC
88.35 0.37
74.31 + 0.23
96.16 + 0.22
Micro-AUC
+.39
74.30
1 0.20
95.35 + 0.28
layers
Micro-AUC
88.49 + 0.43
74.28 + 0.22
96.11 0.18
16

---

Under review as a conference paper at ICLR 2022
A.3 NODE CLASSIFICATION RESULTS
In this section, we show that although DGT is orginally designed for the link prediction task, the learned representation of DGT can be also applied to binary node classification. We evaluate DGT on Wikipedia and Reddit dataset, where dataset statistic is summarized in Table 11. The snapshot created in similar manner as the link prediction task. As shown in Table and Figure DGT performs around 0.7% better than all baselines on the Wikipedia dataset and around 0.7% better than EVOLVEGCN on Reddit dataset. However, the results DGT on the Reddit dataset is slightly lower than DYSAT. This is potentially due to DGT is less in favor of a dense graph, e.g.. Reddit dataset, with very dense graph structure information encoded by spatial-temporal encodings.
Table Comparison of the Micro- and Macro-AUC score of DGT with different number of layers on the woaldworld datasets for binary node classification task.
Method
Metric
Wikipedia
Reddit
Micro-AUC
94.69 0.46
87.35 0.28
DYSAT
Macro-AUC
94.74 0.66
87.36 0.30
Micro-AUC
92.31 1 0.68
84.72 + 0.89
EVOLVEGCN
Micro-AUC
92.36 1 0.85
84.79 -: 0.88
DGT (without pre- pre-training)
Micro-AUC
82.37 0.78
Micro-AUC
92.94 :: 0.62
84.41 + 0.82
Miero-AUC
95.49 - 0.66
85.48 + 0.43
DGT (with pre-training)
Micro-AUC
95.55 + 0.65
85.50 + 0.44
Wilcipedin:
Seddit
staps
0.30
Mooro A15C 0USATIG4.74 60
AUCC Stooe
Macro-ATO
DySAT (87.36
0.30
05..5 9.831
DCT 185,50 0.44)
0.30
Time Strpp
Figure 5: Comparison of DGT with baselines across multiple time steps, where the Macro-AUC score is reported in the box next to the curves
A.4 RESULTS ON NOISY DATASET
In this section, we study the effect of noisy input on the performance of DGT using UCI and Yelp datasets. We achieve this by randomly selecting 10%, 20%, 50% of the node pairs and changing their connection status either from connected to not-connected or from not-connected to connected. As shown in Table 9, although the performance of both using full-attention and 1-hop attention decreases as the noisy level increases, the performance of using full-attention aggregation is more stable and robust as the noisy level changes. This is because I-hop attention relies more on the given structure, while full-attention only take the give structure as reference and learns the "ground truth" underlying graph structure by gradient descent update.
Table 9: Comparison of the Macro-AUC score DGT and its variants with input graph with different noisy level.
Method
10%
20%
50%
Micro-AUC
82.97 + 0.56
81.23
0.78
77.85 = 0.66
DGT (1-hop attention)
Macro-AUC
83.01 + 0.61
82.10 + 0.60
78.43 + 0.67
UCI
Micro-AUC
86.98 + 0.51
86.10 0.57
44.36+0.4
DGT (Full aggregation)
Macro-AUC
8
85.93
0.59
85.51 2.51
Micro-AUC
70.00
0.20
68.55
0.21
65.32 + 0.22
DGT (1-hop attention)
Macro-AUC
69.94 0.20
68.45 0.23
65.61 + 0.15
Yelp
Micro-AUC
70.99 + 0.20
1..44:0.11
70.93 0.21
DGT (Full aggregation)
Macro-AUC
71.64 0.18
71.67 0.21
69.93 0.21
17

---

Under review as a conference paper at ICLR 2022
A.5 COMPARISON WITH CONTINUOUS- LEARNING ALGORITHMS
In this section, wC compare snapshot graph- methods against continuous graph-baset learning algorithm the UCI, Yelp, and ML-IOM dataset. For the continuous graph learning algorithm, choose JODIE Kumar et al. (2019) and TGAT Xu et al. (2020) as the baseline. As shwon in Table 10, JODIE and TGAT suffer from significant performance degradation. This is because they designed to leverage the edge features and fine-grain mne-grained timestamp information for link prediction, however, these information is lacking on existing snapshot graph datasets.
Please note that we compare with continuous graph algorithm only for the sake of completeness. However, since snapshot graph-based methods and continuous graph-based methods require different input graph structures, different evaluation strategies, and are designed under different settings, directly comparing two sets of methods cannot provide much meaningful interpretation. For example, existing works Kumar et al. (2019); Xu et al. (2020) on continuous graph select the training and evaluation set by taking the first 80% of links in the dataset for training and taking the rest for evaluation. In other words, the training and evaluation samples can be arbitrary close and might even come from the same time step. However, in the snapshot graph, the training and evaluation set selected by taking the links in the previous T 1 snapshot graphs for training and evaluating the T-th snapshot graph. That is, the training and evaluation samples never come from the same time step. Besides, since the time steps in the continuous graph are fine-grained than snapshot graphs, continuous graph methods suffer from performance degradation when applied on the snapshot graph dataset due to lack of fine- lin-ggained timestamp information. Due to the aforementioned reasons, existing continuous graph learning methods (e.g., Jodie, TGAT) only compare with other continuous graph methods on the continuous datasets, similarly, existing snapshot graph learning methods (e.g., DySAT, EvolveGCN, DynAERNN, DynGEM) also only considers other snapshot graph based methods as their baseline for a comparison.
Table 10: Comparison of the Micro- and Macro-AUC score of DGT, JODIE on the real-world datasets.
Method
Metric
UCI
Yelp
ML-10M
Micro-AUC
87.91 + 0.32
73.39 + 0.21
95.30 + 0.36
DGT
Macro-AUG
88.49 + 0.43
74.31 + 0.23
96.16 + 0.22
Micro-AUC
57.99 0.34
59.85 0.32
62.84 + 0.47
JODIE
Macro-AUC
57.21 0.37
61.01 0.44
61.30 0.46
Micro-AUC
48.15 + 0.45
51.95 - 0.39
52.15 + 0.51
TGAT
Macro-AUC
49.02 + 0.43
52.78 = 0.40
51.15 + 0.50
B PRE-TRAINING CAN REDUCE THE IRREDUCIBLE ERROR
B. PRELIMINARY ON INFORMATION THEBRY
In this section, recall preliminaries information theory, which are helpful to understand the proof in the following section. More details can be found in books such as Murphy (2022); Cover & Thomas (2006).
Entropy. Let X be discrete random variable, X' as the sample space, and x as outcome. We define the probability mass function as p(x) Pr(X x), X. Then, the entropy for discrete random variable X is defined as
H(X) = - p(x) log logr(z),
(3)
xEX
where we use log base 2. The joint entropy of two random variables X, Y is defined as H(X,))= =-
Σ
p(z.y) log p( y)-
(4)
VE
18

---

Under review as a conference paper at ICLR 2022
H(X.))
H(XA)
((X11)
H(X)
H(Y)
Figure 6: Relationship between entropy and mutual information (Figure 2.2 of Cover Thomas (2006)).
The conditional entropy of Y given X is the uncertainty we have in Y after seeing X, which is defined as
H(Y[X)
(( =x)
ZEX =((XYY) - (X)).
(5)
Notice that have XY = 0ff = f(X), where deterministic mapping.
Mutual information. Mutual information is a special case KL-divergence, which is a measure of distance between two distributions. The KL-divergence between ((x) is defined as
p(x)
KL(plla) Σ p(z) log
(6)
g(x)
2EX
Then, the mutual information T(X;Y Y) between random variable X, Y is defined follows
I(X;Y)= = (p(z,( v)(lp())p(v)) = Σ log p(x,y)
(7)
ZEX p(z)p(z)
and we have I(;;Y) Of Y are independent. Notice that we use I(X;Y) instead of I(X,Y) Y) represent the mutual information between X and Y. Besides, I(X; Y, Z) represent the mutual information between X and (Y, Z).
X,
Based on the above definition entropy and mutual information, we have the following relation between entropy and mutual information:
I(X;Y) = (()) - H(X
-YY H(||X)
(8)
(X) +
and the following relation between conditional entropy and conditional mutual information:
Y(X; H(X H(X|Y,
= H(Y]Z) H(YIX,2)
H(XXZZ) + Z( HXX,YIZ),
where conditional mutual information I ((;YY can be think of as the reduction in the uncertainty of X due knowledge of Y when Z is given.
figure showing the relation between mutual information and entropy is provided Figure 6.
Data processing inequality. Random variables X, Y, Z are said to form Markov chain X - Y if the joint probability mass function can be written as P(x, y, 2) p(z)p(y)a (22g)) Suppose random variable X, Y, Z forms Markov chain X Y Z, then we have [(X; T(X:%).
19

---

Under review as a conference paper at ICLR 2022
Bayes error and entropy. In the binary classification setting, Bayes error rate is the lowest possible test error rate (i.e., irreducible error), which can be formally defined as
P. - E max
p(Y maxp(Y
=y|X)
(10)
where Y denotes label and X denotes input. Feder & Merhav (1994) derives an upper bound showing the relation between Bayes error rate with entropy:
- llog(1 - P.) v H(Y
(11)
The above inequality is used as the foundation of our following analysis.
B.2 PROOF PROPOSITION
In the following, we utilize the analysis framework developed in Tsai et al. (2020) to show the importance of two pre-training loss functions.
By using Eq. 11, we have the following inequality:
-log(1 Pa) S Zx
(12)
By rearanging the above inequality, we have the following upper bound on the Bayes emror rate
1
Pe S exp (H())Z)))
(13)
(a)
exp - -(xx;(x))) (H(Y)-1(2x:)))
- (6) exp +
where equality (a) is due to [[Zx; Y) =( equality (b) is due ((x;
because Zx f(X) is a determin- istic mapping given input X. Our goal is to find the deterministic mapping function f to generate Zx that can maximize [(2x; X) [(x: XJY), such that the upper bound on the right hand side of Eq. 13 is minimized. We can achieve this by:
- X(Y) x (=xx;
and I(Zx:Y\X)
Maximizing the mutual information T(2x; X) between the representation Zx to the input X. Minimizing the task-irrelevant information [(xx; X X), i... the mutual information between the representation Zx to the input X given task-relevant information Y.
In the following, we first show that minimizing Crccon (e) can maximize the mutual information I(Zx; then we show that minimizing Lview )) can minimize the task irrelevant information XYx:
Maximize mutual information / XXx: By the relation between mutual information and entropy X) = (() [ xx). we know that maximizing the mutual information / [(Zx; ; X) is equivalent minimizing the conditional entropy H Zx)x. Notice that ignore H (X) because only dependent on the raw feature and is irrelevant to feature representation Zx. By the definition of conditional entropy, have
H(XIZx)
Σ H(ZZ) =zz)
2,EZx
Σ p(2x)
Σ
-p(x|za) log p(al2z)
e Exx
sEA'
pp(z, Zz) log (()
(14)
E,EXx PEN
Ex(X,2x)
log P(
min Ep(x,
log Qx QX(IZxx)
Qo
< min Bx(x,
log Qo (x
Qo
20

---

Under review as a conference paper at ICLR 2022
where Qo(-I-) is variational distribution with 0 represent the parameters in Qo and KL denotes KL-divergence.
Therefore, maximizing mutual information I X) can be achieved by minimizing Erx.2y [- log Qo (x)] By assuming Qo as the categorical distribution and 0 as a neural network, minimizing Ep Epx.zx [- log Qa (X|2xx) can be think of as introducing a neural network parameterized by 0 to predict the input X from the learned representation Zx by minimizing the binary cross entropy loss.
Minimize the task irrelevant information X Recall that in our setting, input X the node features of (Varga Veenesi and the subgraph induced by (Vunget Veenexi). The self-supervised signal S node features of { (rgget Voonext } and the subgraph induced by (Vragees Veonext). Therefore, it is natural to make the following mild assumption the input random variable X, self-supervised signal S, and task relevant information Y.
A Assumption 2. We assume tall task-relevant information is shared between the input random variable X, self-supervised signal S. iee, we have I(X; (X)) ()= = 0 and [ XX) = O.
In the following, we show that minimizing I(Zx:X] can be achieved by minimizing HZx (S). T Z Y|S)
From Assumption we have (XXY||5) = 0, therefore we know 7(Zx: 5 0. By the relation between mutual information and entropy, we have
From data processing inequality, we have [(X
X
H(xx
H(Zx|Y)
(a)
-[(xx18,Y++1(xxx55)
[[(x))5- + ((xx
(15)
+11x)))++((3x99111
(6)
< H([x|5) -((;S|V).
where equality (a) is due to [X,x Y), = since Zx = f(X) and f is deterministic mapping,
equality (b) is due to [[x, Y|S) = 0, and inequality (c) is due to data processing inequality.
From Eq. 14, we know that
7(Zx|57 = E ( - log P(Zx|S)]
< min Ep(S, log Q' (Zx(s)
(16)
4
By assuming O/ the Gaussian distribution and as neural network, minimizing Eps log Qx [S)] can be think of as introducing neural network parameterized by & that take S as input and output Zs NeuralNetwork,(S). then minimize the mean-square error between Zx and Zs.
C EXPERIMENT CONFIGURATION
C.I HARDWARE SPECIFICATION AND ENVIRONMENT
We run our experiments on a single machine with Intel i9-10850K, Nvidia RTX 3090 GPU, and 32GB RAM memory. The code written in Python 3.7 and we use PyTorch 1.4 on CUDA 10.1 to train the model on the GPU.
C.2 DETAILS ON DATASETS
We summarize the dataset statistic in Table 11. More specifically, we prepare snapshot graphs following the procedure as described in Sankar et al. (2018). In the following, we provide brief descriptions of each dataset.
21

---

Under review as a conference paper at ICLR 2022
Table 11: Statistics of the datasets used in our experiments.
Enron
DRS
UCI
Yelp
ML-10M
Wikipedia
Reddit
Nodes
143
167
1, 1,809
6, 569
20, 537
9,227
11, 000
Edges
2, 347
1,521
16, 822
95, 361
43, 760
157, 474
672, 447
Time steps
16
100
13
16
13
11
11
Enron is public available social network dataset which contains data from about 150 users. We only consider the email communications between Enron employees to generate the dynamic dataset, and use 2 month sliding window to construct 16 snapshots.
Enron '
RDS : This is a publicly available social network dataset that contains an email commu- nication network between employees of mid-sized manufacturing company Radoslaw. Nodes represent employees and edges represent individual emails between two users. The snapshots are created using a window size of days.
UCI dataset": This is a publicly available social network dataset that contains private messages sent between users on an online social network platform at the University of California, Irvine over 6 months. The snapshots are created using window size of 10 days.
Yelp dataset": This is public available rating dataset which contains user-business rating in Arizona. We only consider user-business pairs that have at least 15 interactions. The snapshots are created using a window size of months.
ML-10M': : This is publicly available rating dataset that contains tagging behavior of MovieLens users, with the tags applied by a user on her rated movies. The snapshots are created using a window size of 3 months.
Wikipedia': This is a publicly available interaction graph, where users and pages are nodes, and interaction represents user editing page. The snapshots are created using window size of 3 days.
Reddit : This is publicly available interaction graph, where and subreddits are nodes, and interaction occurs when a user writes a post to the subreddit. The snapshots are created using window size of days. The data from pre-existing, publicly available dataset collected by third party.
C.3 DETAILS ON BASELINE HYPTER- PAREERR-AAMMEERSS TUNING
We tune the hyper- prremeearseeerss of baselines following their recommended guidelines.
!o We use the default setting as introduced in Grover & Leskovec (2016). More specifically, for each node we use 10 random walks of length 80, context window size as 10. The in-out hyper-paramete
p and return hyper-parameter q are selected by geic-search in range {0.25, 0.5, 1, 2, 5) on the validation set. GRAPHSAGE
We use the default setting as introduced in Hamilton et al. (2017). More specif- ically, we train two layer GNN with neighbor sampling size 25 and 10. The neighbor aggre- gation is selected by grid-search from "mean-based aggregation", "LSTM-based aggregation", "max-pooling aggregation", and "GCN-based aggregation" on the validation set. In practice, GCN aggregator performs best on Enron, RDS, and UCI, and max max-pooling aggregator performs best on Yelp and ML-10M.
Phttps://wwil http://cs..cm..ddeeeeeeee..
22

---

Under review as a conference paper at ICLR 2022
DYNGEM and DYNAERNN' We use the default setting as introduced in Goyal et al. (2018)
and Goyal et al. (2020). The scaling and regularization
is selected by grid-search
in range {10-5 6, 10 "]. 3 E {0.1, 2, 5). and 11, E {10 6, 100- 4} the validation set. 1: We use the default setting and model architecture as introduced in Sankar et al. (201 8). The co-oceurring positive node pairs are sampled by running 10 random walks of length 40 for each node. The negative sampling ratio is selected by grid-search in the range {0.01, 0.1, 11, number of the self-attention head selected in the range {8, 16), and the feature dimension is selected in the range {128, 256] on the validation set.
EVOLVEGCN f We use the default setting and model architecture as introduced Pareja et al. (2020). We train both EvolveGCN-O and EvolveGCN-H and report the architecture with the best performance on the validation set. practice, EvolveGCN-O performs best on UCI, Yelp, and MI,100,, EvolveGCN-H performs best on Enron and RDS.
C.4 ADDITIONAL DETAILS ON EXPERIMENT CONFIGURATION
We select a single set of hyper-parameter for each dataset using grid search. More specifically, we select the negative sampling ratio (i.e., number of positive edge/number of negative edge) in the range {0.01, 0.1, J. number of the self-attention head is selected in the range {8, 16), feature dimension selected in the range {128, 256). number of layers the range {2, 4, 63. maximum shortest path parameter that balances the
distance D max in the range {2, 3, 5 on the validation set, and the importance of two pre-taining tasks y 1. The apper-paraeeter for each dataset is summarized in Table 12.
Table 12: Hlper-paramette used in DGT for different datasets. 5_" stands for hyper-paramett parameters that not required.
Enron
RDS
UCI
Yelp
ML-10M
Wiki
Reddit
Self-attention head
16
16
8
8
8
Hidden dimension
256
256
128
128
128
128
128
Number of layer
2
2
6
4
2
2
Hidden feature dropout out ratio
0.5
0.5
0.5
0.5
0.5
0.5
0.5
Self-attention dropout ratio
0.1
0.1
0.1
0.5
0.5
0.1
0.1
Negative sampling ratio
50
10
10
10
10
Maximize shortest path distance
5
5
5
5
5
Mini-batch size
512
512
512
512
512
800
800
During training, we set the target node size as the largest number our GPU (Nvidia RTX 3090) can fit, and sample the context nodes the same size as target nodes. In practice, we found that mini-batch size of 512 works well on all datasets. During the evaluation, we set all validation and testing nodes as target nodes during evaluation. Notice that since gradients are not required during evaluation, therefore into multiple chunks, then we iterative compute the self-attention in each chunk on GPU as shown in Figure 7. Since every iteration only fixed number of self-attention are computed and computing the self- self-attention the most memory-comee coonorr-consuming operation, DGT can inference validation and testing set of any size.
can obtain all the self-attention values by first splitting all self-attentions
D COMPARISON OF DIFFERENT GRAPH TRANSFORMER
In this section, we provide details on the comparison of different graph Transformers as summarized in Table 13, provide detailed information on different positional encoding type in Section D.I, and discussion on othe application of graph Transformers in Section D.2.
bttteea///gttobo...o.////eeeeeer "https://githhin veGo
23

---

Under review as a conference paper at ICLR 2022
M4
13,
MTL
Atteerion provisnely stored mcnnssy
Aftentivn seeds computee
selecual
U5}. Figure 7: Suppose we want to compute the pairwise self-attention between nodes {UI...., , We can first split all self-attentions into multiple chunks, and iteratively compute the self-attention value in each chunk. For example, at the first iteration, we first compute the self attention between node {ui...., 03) (in blue) and store it in memory (in yellow). Then, at the second iteration, compute the attention between node (#1,.... Ca} and node [24, Us}.
Table 13: Comparison of different graph Transformers.
Method
GRAPHORMER
RANNSFORRR
GRAPHBERT
DGT (ours)
Mini- Mitc-
No
No
Yes
Yes
Graph type
Static
Static
Static
Dynamic
Attention type
Full-attentio
1-hop attention
Full-attention
Full-attention
Centrality Encoding
W.-based
Temporal Connection
Encoding type
Spatial Encoding
Laplacian Eigenvector
Intimacy-basee
Spatial Distance
Edge Encoding
Hop-based
D.1 POSITIONAL ENCODING TYPES
In the following, we summarize the positional encoding of different methods.
(1) GRAPHORRMR (Ying et 2021):
Centrality Encoding: the in-degree and out-degree information of each node. Then, they add the degree information the original node feature.
Spatial Encoding: shortest path distance between two nodes. Then, they add the shortest path distance bias term to the self-attention.
Edge Encoding: the summation of all egde features on the shortest path. Then, they add the shortest path distance as bias term the self-attention.
(2) GRAPHTRANSFORMER (Dwivedi & Bresson, 2020) proposes to use the Laplacian Eigenvectors. Then, they add the Eigenvectors to the original node feature.
(3) GRAPHBERT (Zhang al., 2020):
Weisfeiler-Lehman Absolute Role Embedding: the node label generated by the Weisfeiler-Lehman (WL) algorithm according to the structural roles of each node in the graph data. Then, they add the labelled node information to the original node feature.
Intimacy based Relative Positional Embedding: the placement orders of the serialized node list ordered by the Personalized PageRank score of each node. Then, they add the node order information to the original node feature.
Hop based Relative Distance Embedding: shortest path distance between a node to the center node of the sampled subgraph. Then, they add the shortest path distance bias information to the original node feature.
D.2 GRAPH TRANSFORMER WITH OTHER APPLICATIONS
Transformers are also applied to other graph types or downstream tasks. For example, HGT Hu et al. (2020) and GTNs Yun et al. (2019) propose a first-order graph transformer to solve the heterogeneous graph representation learning problem, TAGGEN Zhou et al. (2020) working on synthetic graph generation problems, which are out of the scope of this paper.
24


Reviews:
[{"review_id": "lSTu-HnBJwR", "reviewer": "Reviewer_SMmY", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\nThe proposed method was presented in detail, with many experiments to support the main contribution.\n\nWeakness:\n1. The difference among the three categories classified in \"Dynamic graph representation learning\" could be stated. For example, the second and third classes, according to the authors, only differ from the choice of graph convolution: \"...use self-attention mechanism for spatial and temporal message aggregation. For example, DYSAT (Sankar et al., 2018) replaces the GCN with GAT...\". Rather than the key difference of embedding a dynamic graph, such difference choices are more about neighborhood aggregation (no matter the graph is static or dynamic).\n2. Some sections could be reallocated to make it easier to follow. For example, Section 3.1 could be moved to later sections after introducing basic paradigms, such as \" temporal-union graph\".\n3. It is confusing whether the authors work on static nodes (and dynamic edges) or dynamic nodes. Section 2 defines \"...the t-th snapshot graph Gt(V, Et) is an undirected graph with a shared node set V...\" while Figure 1 (and later presentations) seems to allow different node sets at different time steps.\n4. As the proposed method is claimed to be robust to noises of input data, it would be desired to design experiments to prove this statement. \n5. The scalability of the proposed method could be supported by larger datasets. \n6. As the model complexity relies largely on edge (according to Section 3.1), revealing the consumption on the two (relatively) large datasets, Wikipedia and Reddit, would be more informative (Table 3).  ", "summary_of_the_paper": "The authors designed a graph transformer for dynamic graph link prediction tasks. The model provides a scalable solution to graph transformers, and is claimed to be robust to noise.", "summary_of_the_review": "The paper could be more persuasive on their main contributions for providing more empirical evidence, such as the 'robustness to noise' and 'scalable solution'.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "f8Q6iopOyji", "reviewer": "Reviewer_8DU1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper makes an attempt to study the dynamic graph representation learning. The paper proposes a couple tricks for the combination with graph transformer networks. The tricks include sampling, union graph, pretraining etc. Some experiments have been conducted.\n\nThis paper makes an attempt to study the dynamic graph representation learning. The paper proposes a couple tricks for the combination with graph transformer networks. The tricks include sampling, union graph, pretraining etc. Some experiments have been conducted.\n\nWhile the topic of the paper: time series modeling of graphs is certainly important and needs to be highlighted, i find the paper doesn't really touch upon the core research question of what models are good for time series modeling of graphs, i.e., how the time domain and cross-section domain should be best combined. Instead, the paper mostly focused on a few engineering tricks for applying the transformer architecture and some pretraining tasks. This makes the paper quite disappointing and not so important for the research community, hence, I recommend rejection. This paper is maybe more suited for engineering or Kaggle style conferences, but not ICLR, which should highlight eye-opening scientific research.\n\n1. While the tricks you propose for Transformer is of interest to some Kaggle audience, it's not clear what's the best way to combine time and cross-section domain information. The simplest you can do is either treat each time snapshot as independent samples, and do basic training, this in practice work quite well. You can also use say RNN or TCN etc but unclear whether these will add value. It's also not clear what's the best ways. In this sense, this paper doesn't really touch upon this question at all. Authors need to work on this.\n\n2. Authors need to implement and compare with the efficient Transformer models such as Liformer etc. It's not clear the tricks proopsed can outperform those.\n\n3. If the graphs are quite noisy, say the financial time series, then will attention fail?Since the main focus is on attention, authors need to validate this.\n\n\n", "summary_of_the_paper": "This paper makes an attempt to study the dynamic graph representation learning. The paper proposes a couple tricks for the combination with graph transformer networks. The tricks include sampling, union graph, pretraining etc. Some experiments have been conducted.", "summary_of_the_review": "While the topic of the paper: time series modeling of graphs is certainly important and needs to be highlighted, i find the paper doesn't really touch upon the core research question of what models are good for time series modeling of graphs, i.e., how the time domain and cross-section domain should be best combined. Instead, the paper mostly focused on a few engineering tricks for applying the transformer architecture and some pretraining tasks. This makes the paper quite disappointing and not so important for the research community, hence, I recommend rejection. This paper is maybe more suited for engineering or Kaggle style conferences, but not ICLR, which should highlight eye-opening scientific research.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bU98V3S5RI", "reviewer": "Reviewer_G1X6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The temporal-union graph can significantly reduce the computational costs and memory usage of transformers.\n2. To further reduce the computation on the spatial dimension, a new sampling strategy divides the sampled nodes into two groups called target nodes and context nodes.\n3. The spatial-temporal encoding layer describes a way to encode the spatial and temporal information of a node into the network.\n4. The pre-training method containing a temporal reconstruction loss and a multi-view contrastive loss is proven to be useful to enhance the generalization ability of the model from both theoretical and experimental ways.\n5. Experiment results on two datasets in different applications show the proposed model achieves state-of-the-art performances. Meanwhile, the ablation studies are sufficient to evaluate modules in the DGT. \n\nWeaknesses:\n1. The paper claims its main contributions to the transformers from both its title and introduction section. However, the main body of the transformer in Section 3.4 seems similar to the previous works. Contributions (2) and (3) could be considered as auxiliary methods to improve the transformer. This might be solved by a better paper organization.\n2. An issue of temporal-union graph generation: the method only assumes the dynamic edges but the number of nodes remains static. This may limit the application of the model. Can the temporal-union generation be applied to the above case?\n3. In Section 3.2, this paper divides the nodes into target and context nodes. However, during testing, if all the nodes in the dataset are required to be classified or to predict links (i.e., all nodes are target nodes), it seems that this sampling method and the two-tower transformer will become invalid. \n4. For spatial-temporal encoding, the method is effective but a little complex. It would be better for authors to compare the performance with other straightforward approaches. For example, concatenating the spatial and temporal information to the node, using the raw information as the bias term, or other methods the authors mention in Appendix D.1.\n", "summary_of_the_paper": "In this study, the authors propose a new graph transformer network for dynamic graph representation. To solve the challenges of static graphs learning and the temporal information aggregating, this paper introduces a Dynamic Graph Transformer (DGT) which contains three components: (1) a two-tower Transformer-based method, (2) temporal-union graph construction (3) a complementary pre-training task. Extensive experiments on the two datasets of link prediction and node classification demonstrate the superiority of the model. The ablation studies justify the effectiveness of each module in the DGT model.", "summary_of_the_review": "This work proposes a new DGT for dynamic graph representation. All the claims of existing challenges and their corresponding solutions are correct. The novelty of this work is moderate and the experiments on two datasets justify the superiority of the model. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UVtaV2WNgE", "reviewer": "Reviewer_uub9", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: \nThe paper proposed a temporal-spatial encoding to capture implicit edge connections.\nWeaknesses:\n1. This paper investigates the methods for dynamic graph representation learning. However, some closely related methods are not discussed and not compared in this paper, e.g.,\nhttps://storage.googleapis.com/pub-tools-public-publication-data/pdf/19698cbb225b3fc165231dd2fc6f0483ff28a777.pdf,\nhttps://snap.stanford.edu/jodie/\netc.\nThe authors are suggested to compare with or at least discuss these work, which could provide a more comprehensive discussion for the paper.\n\n2. The paper lacks some standard datasets that are widely utilized in this topic, e.g., MOOC and LastFM (https://snap.stanford.edu/jodie/). The authors are suggested to utilize or at least discuss these datasets, which could help the readers to compare the proposed method with the existing ones.", "summary_of_the_paper": "In this paper, the author focused on the problem of dynamic graph representation learning and proposed a temporal-union graph structure and a target-context node sampling strategy. Experiments show that this work performs well in some real-world datasets.", "summary_of_the_review": "In this paper, the author introduced a DGT for dynamic graph representation learning to leverage the graph topology and capture implicit edge connections. For the weaknesses, it is suggested to provide more concrete experimental results to better validate the effectiveness of the proposed method.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this study, the authors propose a new graph transformer network for dynamic graph representation. To solve the challenges of static graphs learning and the temporal information aggregating, this paper introduces a Dynamic Graph Transformer (DGT) which contains three components: (1) a two-tower Transformer-based method, (2) temporal-union graph construction (3) a complementary pre-training task. Extensive experiments on the two datasets of link prediction and node classification demonstrate the superiority of the model. The ablation studies justify the effectiveness of each module in the DGT model. The reviewers has various technical issues with the paper which the authors mostly addressed (e.g., whether the nodes are static or dynamic, whether DGT is robust to noise, whether it scales to larger datasets). Overall, the contributions seem incremental. There is confusion among the reviewers as to whether the proposed model differs from prior art. It seems to me there actual  differences  but whether they major or minor is open to interpretation. Overall there reviewers were not particularly excited about model/results/contributions.
Decision: Reject