Learnable Spatial-Temporal Positional Encoding for Link Prediction
Authors: Katherine Tieu
Dongqi Fu
Zihao Li
Ross Maciejewski
Jingrui He
Venue: ICML 2025 poster (2025)
Keywords: Positional Encoding
Link Prediction
Transformer
Primary area: deep_learning->graph_neural_networks

Abstract: Accurate predictions rely on the expressiveness power of graph deep learning frameworks like graph neural networks and graph transformers, where a positional encoding mechanism has become much more indispensable in recent state-of-the-art (SOTA) works to record the canonical position information. However, the current positional encoding limits in three aspects, at least: (1) most positional encodings are pre-defined, and fixed functions, which are inadequate to adapt to the complex attributed graphs; (2) a few pioneering works propose the learnable positional encoding but still limited to the structural information, leaving the real-world time-evolving topological and feature information untouched; (3) most positional encodings should be equipped with transformer's attention mechanism to fully release the power, where the dense or relational attention is often unaffordable on large-scale structured data.
Hence, we study the possibility of Learnable Spatial-Temporal Positional Encoding in an effective and efficient manner and then propose a simple temporal link prediction model named L-STEP. Briefly, for L-STEP, we (1) prove the proposed positional learning scheme can preserve the graph property from the spatial-temporal spectral viewpoint, (2) verify that MLPs can fully exploit the expressiveness and reach Transformers' performance on that encoding, (3) change different initial positional encoding inputs to show robustness, (4) analyze the theoretical complexity and obtain less empirical running time than SOTA, and (5) demonstrate its temporal link prediction out-performance on 13 classic datasets and with 10 algorithms in both transductive and inductive settings using 3 different sampling strategies. Also, L-STEP obtains the leading performance in the newest large-scale TGB benchmark.

Learnable Spatial-Temporal Positional Encoding for Link Prediction
Katherine Tieu Dongqi Fu
Zihao Li"
Ross Maciejewski
Jingrui He
Abstract
TGB benchmark. Our code is available ht //github... http://t.ccoo////////t// wow./thrnn2//1 STEP.
Accurate predictions rely on the expressiveness power of graph deep learning frameworks like graph neural networks and graph transformers, where positional encoding mechanism has be- come much more indispensable in recent state-of- the-art works to record the canonical position in- formation. However, the current positional encod- ing is limited in three aspects: (1) most positional encoding methods use pre-defined, and fixed func- tions, which are inadequate to adapt to the com- plex attributed graphs; (2) a few pioneering works proposed the learnable positional encoding but are still limited the structural information, not considering the real-world time-evolving topolog- ical and feature information; (3) most positional encoding methods are equipped with transform- ers' attention mechanism to fully leverage their capabilities, where the dense or relational atten- tion often unaffordable on large-scale structured data. Hence, we aim develop Learnable Spatial- Temporal Positional Encoding in effective and efficient manner and propose simple temporal link prediction model named L-STEP. Briefly, for L-STEP, we (1) prove the proposed positional learning scheme can preserve the graph property from the spatial-temporal spectral viewpoint, (2) verify that MLPs can fully exploit the expressive- and reach transformers' performance that encoding, (3) change different initial positional encoding inputs to show robustness, (4) analyze the theoretical complexity and obtain less empiri- cal running time than SOTA, and (5) demonstrate its temporal link prediction out-performance on 13 classic datasets and with 10 algorithms in both transductive and inductive settings using differ- ent sampling strategies. Also, L-STEP obtains the leading performance in the newest large-scale
1. Introduction
Link prediction is an important research topic in the graph learning community (Kumar et al., 2020), especially com- plex networks (Lu Zhou, 2010; Martínez et al., 2017). Learning from the time-evolving topological structures and time-evolving node and edge features, and determining whether the link (i.e., edge or interaction between two nodes) exists at certain timestamp are challenging (Tieu et al., 2025) but have attracted much research interest from dynamic protein-pree protein interactions (Taylor et al., 2009; Gupta et al., 2015; Fu He, 2022: Zhou et al., 2022), rec- ommender systems (Huang et al., 2005; Cong et al., 2023), social network analysis (Daud et al., 2020; Fu al., 2020; 2023), and many more, real- world graphs often exhibit temporality (Fu et al., 2022; Li et al., 2023; Lin et al., 2024; Ban et al., 2024; Tieu et al., 2024; Li et al., 2025a;b), and heterogeneity (Le et al., 2024a; Liu et al., 2024; Le et al., 2024b; Zhong et al., 2024; He et al., 2025).
Recently, with the success of the attention mecha- nism (Vaswani et al., 2017), graph transformers have been proposed for the structured data to obtain the out- performance in many graph applications (Rampásek et al., 2022; Kim et al., 2022; Fu et al., 2024). To preserve the exact ordering information, the corresponding positional en- coding plays an important role in boosting the downstream task performance like temporal link prediction. Recent stud- ies show that it can only help graph transformers (Yu et al., 2023) but also can contribute graph neural net- works (Cong et al., 2023). In spite of the great potential, the research on positional encoding on graphs is limted from at least three aspects. First, following (Xu et al., 2020), most positional encoding methods are still based on pre- defined, and fixed functions, which either heavily depends on the domain knowledge of understanding the topologi- cal distribution of graphs not easy adapt to different complex attributed graphs. Second, to the best of our knowl- edge, a pioneering work (Dwivedi et al., 2022) proposed the learnable position encoding to tackle this problem, but it only considers the static structural information and does not accommodate the realistic time-evolving structural and
Equal contribution Universstyy of Illinois Urbana- Chaaman-a e Meta AI AAiizna State University. Correspondence to: Jingrui He <jingrui @ ill.
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learnable Spatial-Tempord Positional Encoding for Link Prediction
feature information. Third, most, if not all, of the positional encoding methods need to rely on the transformer's atten- tion mechanism to fully release the expressiveness power. To be more specific, in order to preserve the long-distance relation into the representation vectors, graph transformers usually need high time complexity due to the dense atten- tion or relational attention (Müller et al., 2023; Min et al., 2022), i.e., each pair of nodes need to be attended with Onn)) time complexity, which can even approach ((n) in more complex relational setting (Diao & Loynd, 2023), and the prolonged time-aware features also increase the size of neural architectures. A detailed theoretical time complex- ity and empirical running time comparison with SOTA can be found in Appendix and Appendix H.3.
and the edge features associated with an event (u, v; as e Rds, where dx and dg are the dimensions of the node and edge features.
Temporal Neighbors. The temporal neighborhood of a node u E V at time t E (1...., .T)...,),.. denoted as Nu, is the set of all interactions that involve u at time t. Formally, Ni can be mathematically expressed as No = {(u, v. t.)) e V4; (u, e, E E"
Time Encoder. A time encoder is a function to obtain the vector representation of time I. (Xu et al., 2020; Wang et al., b021b; Cong et al., 2023). Let dr be the dimension of the time encoding vector. We define our time encoding function as fr : RR+ + Rdr, In L-STEP, for cos(t w). where w E Rdr with the 7th entry computed as wi a (1-1)// and a IR are hyper-parameters. In order to enhance the ability of dr in distinguishing all timestamps, given that lmaz is the maximum timestamp being considered, a and B should be selected in such a way that maa a - 1)/B + 0 as i goes towards dy. Moreover, at 3, and w are fixed during the training process of L-STEP.
R [r() =
In light of the above discussion, we aim to propose learnable positional encoding evolving over time, such that simple neural architecture can achieve competitive or even the same performance as graph transformers. Thus, we first propose two major novel techniques: Learnable Positional Encod- ing Module (LPE) and
Encoder based on Discrete Fourier Transform. Then, we combine these two into an end-to-end temporal link prediction frame- work named L-STEP, as illustrated in Section 3.
Positional Encoding for Graphs. Originated from the transformer (Vaswani al., 2017), positional encoding is proposed to add node feature information to support the attention mechanism by indicating the relative position of a node within the input graph (Dwivedi et al., 2023), and the common positional encoding methods include computing the Laplacian eigenvector or Personalized PageRannk vec- tor for each node (Rampásek et al., 2022; Chen al., 2023). Mathematically, given n-node (static) graph G (V, F) and its adjacency matrix A E =x the normalized Lapla- cian of G is computed as L I, D D-112 D-1/2AD 1/2 where I, is the n x n identity matrix, and D is the diagonal de- gree matrix of G. Let the sigen-decompossitonn of L be L = UAUT, where onal matrix consisting of L's eigenvalues and U consists of n eigenvectors of L as its columns. Let u, E R" be the 7th eigenvector of L and its jth entry denoted as u.j- Then, the positional encoding of node i E V is defined as p = [ui.i...., un.s] E R". In practice, the dimension dp of positional encoding is usually set to be less than n for computational efficiency (Dwivedi & Bresson, 2020), i.c., dp < n and p [u.,:....; Udp.i) E Rdr.
To be specific, we first prove that the proposed positional encoding method LPE can preserve the temporal graph topology from the spatial-temporal spectral viewpoint and L-STEP having better theoretical runtime complexity com- pared to SOTAs in Section 4. Moreover, in Section 5, we evaluate the empirical performance of L-STEP exten- sively, including (1) the comprehensive effectiveness com- parison with 13 classic datasets, 10 algorithms, 2 learning settings (transductive and inductive), and 3 sampling strate- gies, where our L-STEP performs the best across the board, (2) the verification of the role of MLPs and transformers upon L-STEP, (3) the learning robustness of L-STEP in terms of different initial positional encoding imputs, (4) pa- rameter analysis, running time comparison, and ablation studies, and (5) the leading performance in the large-scale TGB open benchmark (Gastinger et al., 2024).
diag(A A2. .n. is a diag-
2. Preliminaries
Here, we introduce preliminaries to pave the way for deriy- ing our L-STEP in the next section.
Discrete Fourier Transform. To pave the way for learnable positional encoding, need to first introduce the basics of Discrete Fourier Transform (DFT) (Sundararajan, 2001). In brief, DFT is designed to convert a finite-length sequence of samples into another sequence in the frequency domain (with the same length). Formally, given a sequence with length N, (xx ) the DFT operation F((x,) 1 con- verts {x,} to the complex-valued sequence (X,],², as X, = EN= X&e 127 &k. Also, to re-construct the original
Temporal Graph Snapshot. A snapshot of a tempo- ral graph G is collection of temporal interactions (i.e., edges) at time & E (I....,,T, Ty, which is defined as G = {(u, v, tllu E V' E (u, v,t) E E*). Each event (u, v, t) denotes an interaction between nodes u and v that occurs at time t, and the node and edge sets of G* denoted as Vt and Et respectively. Additionally, for node u E V*, we denote the node features as s dddv
2

---

Learnable Spatial-Temporal Positional Encoding for Link Prediction
sequence { inverse DFT (IDFT) (- ((x,)=))) is defined as x Σ 1= 2
spectral viewpoint in Section 4), (2) and avoids comput- ing the Laplacian eigendecomposttion for each timestamp from scratch, which is computationally expensive (e.g., O(1V19) (Chen et al., 2023) or ((E))3)) (Dwivedi et al., 2023))
3. Proposed Method: L-STEP
To hegin with, we focus on a general research question, i.e., given two nodes u and v, how can we predict whether the link (interaction or edge) exists between u and u at a certain timestamp effectively and efficiently?
Because of no peeking at the current graph topology struc- ture and features, our LPE is an iterative updating module. Next, we introduce LPE in two-folds: positional encoding, how LPE approximates the current positional encoding (that will be used to determine links by Vode-Linn-Posttionnal Encoder in Section 3.2), and (2) how to store the approximate positional encoding and up- date/optimize it in the future round with current topology structure and features observed.
(1) given the past
To answer this question, we propose simple temporal link prediction model named LTS... It retrieves the interac- tion history of two nodes and decides whether the current link exists or not. Without heavy neural architectures like dense attention (Rampásek et al., 2022) or relational at- tention (Diao & Loynd, 2023), L-STEP only depends on two of our proposed simple yet effective techniques, i.e., Learnable Positional Encoding Module (LPE) and Node- Pon-PPosiiioaal Encoder, such that L-STEP can preserve the spatial-tempong topology rigorously (as shown in Sec- tion 4) and outperform attention- based state-of-ther thettheart link prediction methods (as shown in Section 5).
Approximating current position encoding. First of all, we denote the positional encoding of to be learned for time t as p', E Rdr. Suppose there are L, most re- cent distinct timestamps prior to t, i.e., fi...., ,Y (where tj < <... < tly < tt, and we can retrieve the already learned {pa (p....., p that is regarded as L-length sequence. Ad- ditionally, considering computational efficiency, we only retrieve I. most recent timestamps. Then, in this LPE mod- ule, we leverage the Discrete Fourier Transform to capture the temporal dependencies among ......, .P and derive an estimated positional encoding of u at time t denoted by Pt. E Rddr.
The overall framework of L-STEP is shown in Figure about how retrieve and learn from history to make the current decision with two proposed techniques. Next, we will introduce the details of the proposed techniques, i.e., Learnable Positional Encoding Module in Section 3.1 and Node-Link PonkkPoosiional Encoder in Section 3.2.
way
To be specific, we start by applying Discrete Fourier Trans- form (DFT) on the sequence {pr { to obtain the corre- sponding sequence in the frequency domain. Then, em- ploy a complex- vvluud learnable filter, W Wittter I to filter out noises of the sequence in the frequency domain, (detailed discussion on how positional encoding could be regarded as signals and what kind of noises that our LPE module filters can be founded in Appendix D) and finally transform back to the original domain. The process can be mathematically expressed
3.1. Learnable Positional Encoding (LPE) Module
The main idea of Learnable Positional Encoding (LPE) is to leverage historical positional encoding to determine whether the link exists at the current timestamp. However, learning from the history data in an effective and efficient way and only through positional encoding challenging, because SOTA methods usually need complex attention mecha- nism (Poursafaei et al., 2022; Yu et al., 2023).
To this end, we aim to only use positional encoding to carry informative and useful knowledge to record what had happened in the past (e.g., what interactions occurred and what the node and edge features looked like around the interaction). Existing simple hand-crafted positional encod- ing can be efficient but tend to induce suboptimal perfor- mance (Wang et al., 202 lb; Cong et al., 2023).
pp F (Wyatter falter C F(IP)))))) (I)
Then, we obtain the approximate positional encoding ph, by applying sum poollpooln with learnabee weights on (p 1 1==1
p
P
W
Thus, we propose a "learnable" positional encoding module (LPE), enabling it to reflect complex and non-linear knowl- edge. As shown in Figure 1, in our L-STEP, LPE estimates (or approximates) the positional encoding at current time by applying the Fourier Transform (with learnable parame- ters) on the past positional encoding. It is worth noting that obtaining the positional encoding through LPE: (1) records the complex spatial -emporlll information (proved from the
where Wpm.. Lx111 Note that the approximate posi- tional encoding Pt, will be sent to the -ode-Link- Liik--positional Encuder (in Section 3.2) for making predictions for current time t.
Storing approximate positional encoding for future re- trieval and optimization. Since L-STEP does not peek at the current topology structure and features when making the
3

---

Learnable Tentpalle Positional Encoding for Link Prediction
G
node
mode 14
1-hop neigh.
1-hop neigh,
Retrieve History Node Feature Eo.
G
P
Save for Next Update
Es 151
History Encodlng
Appregate History Edge Fealure
hu,
Eq
Approximated Encoding
DFT F
IDFT F
Pooling
Pooling
P
Lo. (b)
h N
C+i-a
u
ta I
p
Append Time Encodiing with Neighbors
Pooling
h
h
Spatial- Temporal Assregation
h
Do
Link Predictor
hu
0%
P
Learnable Positional Encoding (LPE) Module
Node-Link-Positionna Encoder
Figure Overall Framework of L-STEP
prediction for now, i.e., only using approximate positional encoding Pa, we claborate on how the current approximate positional encoding gets updated and optimized in the next round.
positional encoding of its recent 1-hop neighbors prior to time t, and, eventually, derive a compact representation associated with that encodes all the information.
In general, Mode-Link-PPsitionns Encoder works follows. We first use h and h denote the node and link en- coding of recent 1-hop neighbors of node u. Then, we apply MLP transformations on h and h i to obtain the encod- ing, denoted by h hi.NJI which represents the combination of node-lind link information. For adding positional information, we use h p to denote the aggregated positional encoding of recent 1-hop neighbors, and further transform them by MLP layers. Eventually, h bi, and h are combined by 1-layer MLP derive a temporal representation at time t for u, denoted by h which will be sent together with h to the link predictor in Section 3.3 to determine whether the link exists between nodes and at time t.
After making the current link predictions time (as shown in Section 3.2), L-STEP can then "peek" (or "reveal") the ground-truth links at time t, such that it can update the approximation P into updated pt for future retrieval and predictions.
Then, we need to update the positional encoding of for any node at f. We sample the most K recent inter- actions, including those that occur at time t if the node has interactions at time t. Suppose they are indexed as {(ū1, E.)..... (ūx, u,tx)} where t < .... < fx I Leveraging the approximate positional encoding from ú1 ūk. pt, derived as
The detailed computational procedures of the Node-Link- Positional Encoder are explained below.
P = P +anh taanh( (eel)) P. W RELU(W (1)
)
E Rd
(3)
First, the node encoding of recent 1-hop neighbors of can be obtained by aggregating features of nodes that interact with in the time interval [t tyapi f), where tgap is dataset-dependent hyper-parameter. Mathematically, this process can be described as
where C. = - 1,)) II TI E ddp
fr is the time encoder, and w (ddxxdr)dr)) w
E
ddexdp w( dddxde are MLP parameters.
At the first time lo. we denote the initial positional encoding as the Laplacian of the initial graph snapshot Goo, Formally, let be the Laplacian of te and the eigen-decomposition of be UAUT, then t = [uj.u..... udp. dr where u; is the 7th eigenvector of L, as defined in Section
W = s + (u', u,, E N .... U...)
(4)
3.2. Loade-Link-Posttionn Encoder
where s is the input node features, and Mean(-) ( is the mean pooling operation.
For node u, the Node-Link Link-Positional Encoder is designed to aggregate its historical node and edge features with the
Then, we derive the link encoding for by extracting the

---

Learnable Spatial-Temporal Positional Encoding for Link Prediction
K most recent interactions involving u that oceur prior to time i, combine the edge features and the time encod- ing of these interactions, and further apply MLP trans- formations on these representations. Specifically, sup- pose the K most recent interactions of u are indexed as {(1, u, (1),..., (ug, u, k,), where t ..... t'x < Let H., E [x(((drdd)) be a matrix, whose hthh row is defined as [H v, ElK = [[fr(t - (()) (e (e(,u;)
and at time and train L-STEP against the ground truth connections before t.
Link Predictor. Given node pair (u, v) and timestamp t, L-STEP's goal is to predict whether there is a link between (u, u) at time t. Specifically, the Link Predictor would give the probability D E (0, 1) of whether u and v interact at time t by
R ((((dd))ss) where [-I--] denotes concatenation, fr is the time encoder, and u. denotes the edge features. If u does
0 = sigmoid (2) (2 RELU (I)))
(10)
not involve least K interactions before then H 5 is zero-padded so that the matrix has K rows. We first apply 1-layer MLP on the last dimension of H sum-pool over K rows of H with learnable weights obtain vector of dimension dr dg, and finalize the encoding with additional 1-layer MLP transformation
where sigmoid denotes the sigmoid function mapping all real values to the range (0, 1), and w()
R (22dx)xxx W(2) E RdNx are 1-layer MLPs.
Loss Functions. To begin with, we point out the necessary components of the objective loss function for the training process of L-STEP, give formal definitions for those compo- nents, and derive the final loss function used in the training process of L-STEP.
h E
w(2)
(2) link (RELU((H W(1)
Wirr)) link
E Rdrtdg
link
(5)
where W (1)
links w E (gdrrdds) and Waum E
Suppose there are B positive (i.e., existing edges) samples
(pos) (uf2or) 11 .t),.... (u (pos) (pos)
R xxx1_
.BB .tg) and B negative (i.e., non-existing edges) samples (ug (neg) (neg) ,t),,..., (neg)
After that, h "NNIE is obtained by a 1-layer MLP transfor-
: .BB _ .tB). We employed 3 different negative sampling strategies (NSS): random, historical, and inductive; more details can be found in Appendix I.I. Specifically, following (Yu et al., 2023), during the model training stage, we employ random NSS for the loss function computation, and then evaluate model with all 3 NSS. Thus the ground truth label for the positive samples should be 1, and 0 for the negative samples. As the link prediction can be regarded as a binary classification problem, we employ the binary cross-entropy loss function obtain the link prediction loss Lip as
mation as
h N E
WNjEe(( (,, O h2, )² Rdx
(6)
where W WNIEE tdd
Next, for historical positional information, we apply sum aggregation over the positional information from the afore- mentioned K most recent interactions involving u as
K
h h2P
-E(or(t-G)) j=1
1I TTT E RRd (7)
where fr is the time encoder. Let w Rd
Lip 2B
-1 (
Σ i=
log (in,emer,, toues (pppor) sppooo))
w(? E ddp (self) E Rd and tanh be the hyperbolic tangent function. Then, h obtained through the biighborhhoodaggregguee positional encoding hi,P P
(11)
B
Σ log (1 (ngnea)
and
p% as
where Deppor) .ufro)) denotes the predicted probability of
h = PL. +lanhan(()))
w (sel mf P. + WW (1)
link existing between (pos) [pos) at time 4; as defined in Eq. 10, and i (ymn)) .uf (.(=ao) is the predicted probability of a
(8)
.v,
Finally, the temporal representation at time of u, h is derived as
link existing between u. (neg), of (((eg) at time t,. Thus, ideally, i (g(pos)) of (poa) should be close 1, and U,, (ees)) (eee), (nee) should be close to zero.
hi = W[( hy ( (1 JJT E Rdv
(9)
where We e (dv+)d))
In addition, we introduce the positional encoding loss Lp to assess the learned positional encoding, defined in Eq. 2. Specifically, we would expect p a
3.3. Optimization
(pos)> as (pos) at time f, Thus, the D soa) lla (where || ||2 denotes the
(pos)
be close to p of
(pos)
With the two embedding vectors h and hi, we can now let LTST decide whether link exists between nodes u
there is a link between u,
difference |p u (poa)
5

---

Learnable
Positional Encoding for Link Prediction
2-norm of a real-valued vector) should be small, so that the learned positional encoding correctly reflects the nature of positional encoding. Moreover, in order to avoid L-STEP giving similar positional encoding to all nodes to minimize the aforementioned 2-norm difference of positive samples, we add another constraint, i.e., maximizing the difference 2/ P"meeoll where Oneg is a positive scaling D
future graph snapshots without leveraging the information about the future graph topology.
Note that the above statements do not necessarily mean that L-STEP does not need to update the positional encoding in every case. Actually, L-STEP indeed updates the positional encoding when new interaction happens. The role of Theo- rem 4.1 demonstrate the effectiveness of our positional encoding in the inductive setting, where the future scenario is usually not given or difficult to observe.
Onen (mew))
,ug (nea) .g) are not all possible negative links (i.e., not connected), we let < Oneg < to avoid L-STEP emphasizing the negativity of these B negative samples, Therefore, we define the positional encoding loss
(meg) factor. As (u) (u( 2i (mes)) tt),...,, (u. (neg)
Complexity Analysis. Next, we provide the analysis on L-STEP's computational complexity. L-STEP con- sists of two main components: LPE Module and Node- Link-Positional Encoder. In LPE Module, the approx- imated positional encoding is derived by applying Dis- crete Fourier Transform on L-length sequence of previ- ous positional encoding, so the complexity is OL log(L)), (L))))()) achieved by utilizing Fast Fourier Transform. Then, we update the positional encoding by sampling the K most recent interactions, adding O(K) time. Therefore, for n nodes, LPE Module costs (nn(L + K)). For Node-Link-Position
1 B
ppe
1
P (po)
(12)
B
Oneg
11p
(nes)
p
P llz
of
Finally, the overall loss function is
Encoder, for each node we retrieve node-level information from its neighborhood in the in- terval [t gup: t and sample its K most recent interac- tions, so the complexity is O(n (fgap + K)), which can be achieved by pre-computing all temporal neighbors in the range [ - 14yap; 1) of each node. Thus, the total time complexity is (nn(tpap + K + L log(L)), which scales lin- early with the number of nodes, as L, K, tgap are constants independent of n.
L = (1 pe Cip + ape Spe
(13)
where Oppe E (0, 1) is the weight for Cpe. The training procedures of L-STEP can be found in Ap- pendix
4. Theoretical Analysis
In this section, we first theoretically show that, at time f, the approximated positional encoding p', defined by Eq. 2, can be a good approximation of the positional encoding of graph snapshot G" by establishing a bound for the approximation error.
Compared to recent SOTA, DyGFormer (Yu et al., 2023) and FreeDyG (Tian et al., 2024), L-STEP is more efficient as both of these methods employ neighborhood co-occurrence for each node pair of interaction, making their worst-case complexity scale with the number of edges, |E]; while L- STEP's complexity scales with n, the number of nodes, and it is quite common that n << [E]. showing L-STEP's advantage in efficiency. Detailed theoretical time complex- ity comparison can be found in Appendix E, and detailed empirical running time comparison can be found in Ap- pendix H.3.
Theorem 4.1. Suppose the temporal graph G is "slowly changing" " (i.e., the ground truth positional encoding p a 2s p' )1) then the corresponding approximated posi- tional encoding of L-STEP satisfies
1p PC' Se
(14)
where t" > t is the future distinct timestamp of t, and is a bounding term that depends on L,, which is the number of recent graph snapshots utilized in obtaining the approxi- mated positional encoding, as stated in Eqs. and 2. (Proof in Appendix C)
5. Experiments
Here, we provide the main results showing the outperfor- mance of L-STEP in classic and large-scale benchmark datasets. Furthermore, we leave
the effectiveness comparison in more learning and sam- pling settings in Appendix H.I.
Briefly, Theorem 4.1 indicates that when the graph is slowly
changing, the positional encoding learned at the previous
MLPs and Transformers performance on the proposed
timestamp can well preserve the next close future times- tamp's positional encoding. In other words, as Theorem 4.1
LPE positional encoding method in Appendix H.2, running time comparison with SOTAs in Appendix H.3,
suggests, the positional encoding function of L-STEP can
LPE ablation studies wrt input node and edge features in
be a good representation of the positional information of
6

---

Learnable Opatial-Temporsy Positional Encoding for Link Prediction
Table 1. Performance comparison in the transductive setting with random negative sampling strategy.
Metric
Dalavets
JODIE
DyRep
TGAT
CAWN
TCL.
GraphMixer
DyGFuemer
FreeDyG
LSEEP
Wikipedia
96.50 0.14 94,86 + 0.06 96.34 + 0.06
98.45 + 0.06
98.76
+0.03
0,116
97.25 + 0.03 99.03 0.02
0.01 99.34
0.04
Reddit
98.31 0.14 98.22
0.04 98.52
0.02 98.63
+ 0.06
99,11
00001
97.53
97.31 0.00 99.22
0,01 99.37 99,48
0.04 0.04
MOOC
80.23 2.44
0.49
85.84
89.15
= 1.60
80.15
0,23
82.78
0.45
89.61
0.39
LasFM
2.11
71.92
73.42
0.21
77.07
4.97
0.06
67.27 2.16 75.61
0.24
93.00
0.10
9.15 96,06
0.30
Enron
84.77
8.36
0.97 86.53
09.56
0.77
0.12
9.17
9251
93.96 0.36
Social Evo.
89,89
0.38
0.17 93.57
0.17 84,96
93.13
93.37
94.73
94.1
92.22 0.25
UCT
89.43+
1.09 63.14
79.63
0.70
92.34
1.04
00
89.57 + 1.63 93.25 +: 0.57 96.79
96.28
0.11
96.67 0.47
AP
Flights
95.60
0.72
0.10
97,95
0
9.51
91223 90.99 0 98.91
98.1
98,94 0.10
Can. Parl.
0.31 66.54
70.73
70.88
69.8
6867
2.67 77.04
97.36
2,47
98.24 0.11
US Legis.
75.05 + 1.52 0.39
75.99
0.58
70,58
0.48
69.
0.48 70.74
1.02
71.11
69.94
0.59
76.74 0.60
UN Trade
64.94 0.31 0.93
61
0.18
65.03
1.37
0.12
62.21
# 0.03
62.61
0.27
75.84 + 2.08
UN Vore
0.81
62.81
52.21
+ 65.72
2.17
0.10
$1.90
0.30
52.11
0.16
55.55
$1.99
: 1.13
73,40 0.03
Contact
95.31 1.33 +0.15
96.28
0.09
96.89
90.26
+ 0.28 92.44
0.12 91.92
0.03 98.29
97.99
0.03
98.16
0.09 1,85
Avg. Rank
6.77
7.38
1:25
4.08
5,85
8,46
6.77
2.77
3.85
Wikipodia
0.07 94.37
:: 0.09
96.67
+ 0.07
98.37
0.07
98.54
- 0.04
95.84
= 0.18 96.92
= 0.03
98.91
0.02
99.41
41 0.01
99.48 + 0.03
Reddit
98.31 0.05 98.17
0.05 0.05 98,
1:
0.02
98.60
0.06
99.01
0.01
97.42
1 0.02 97.17
-: 0.02 99.19
0.01
99.
0.01
99.49 1: 0.03
MOOC
83.81 1.209 85.03
87.11
91.21
80,38
0,26 83.12
0.18 84.01
87.91
0.35 89.28
LastFM
70.49 71.16
1.8 71.59
+: 0.18 78.47
- 2.94
85,92
64.06
1.16 73.53
93.05
0,10 93,42
0,15 97.52 + 0.17
Enrea
87.96 1: 0.52 84.89 3.00
68.89
1: 1.10 88,32
1: 0.99
0.14
75.74
1: 0.72 84,38 1: 0.21 93.33
94,01
1
0.11
95.98 1 0.23
Social Evo.
92.05 1. 0.46 90.76 0:21 94,76
1 0.16 95.39
1 0.17 87.34
0.08
94.84
1 0.17 95.23 1 0.07 96.30 1 0.01
96.59
0.04
94.33 1. 0.21
ROC-AUC
-: 0.49 2.33 78.53
1: 0.74 92.03
0308
87,82
= 91.81
94,49
0.21
97.62
Flights
96.21 1: 1.42 95.95 0.62
94,13
1: 0.17 98.22
1. 0.13 98.45
03.45.0000
0.01 91,21
1: 0.02 91.13 1: 0.01 98.93 1 0.01 98.03
0.17 99.38
1. 0.04
Can. Purl.
78.21 1. 0.23 73.35
1 3.67
75.69
1 0.78 76.99
1 1,80
75.70
3,27
72.46
1 3.23 83.17 1 0,53 97.76
1 0.41 81.09
1 2.28
98.97 1 0.06
US Legis.
82.85 + 1.07 82,28
1: 0.32 75.84
+ 1,99 83.34
1: 0.43
0.39
76.27
2 0.63 76.96 - 0.79 77.90
0.58 77.26
1 0.50
83,89 1 0.43
Trude
69.62 0.44 67.44
0.83
64.01
1. 69.10
68.54
64.72
0.05 65.52 1: 70.20
1.44
83.17 1: 1.28
UN Vote
68.53 + 0.95 67.18
+ 1.04
52.83
+ 1.12 69.71
+: 2.65
53.09
0.22
51,88
= 0.36 52.46
= 0.27 57.12
0.62
52.79 # 1.56
79.59 + 0.02
Contact
96.66 + 0.89 96.48
1 0.14
96.95
1: 0.08
97.54
+ 0.35
89.99
1 0.34
94.15 + 0.09
93.94 = 0.02
98.53 - 0.01
98.39 1 0.02
98,72 1: 0.06
Avg. Rank
6.08
7.31
7.46
3.92
6.0
8.69
7.15
3.0
3.69
1.69
Appendix H.4,
Under the transductive setting, models will predict the link occurrence in future timestamps between nodes that had been observed during the training process, while the induc- tive setting involves predicting future links between unseen nodes in the training process. For each setting, we use two evaluation metrics: Average Precision (AP) and Area Under the Receiver Operating Characteristic Curve (AUC-ROC). In addition, following (Poursafaei et al., 2022), for more ro- bust evaluation, each baseline is assessed with three negative sampling strategies (NSS): random, historical, and inductive (Details in Appendix I).
analysis of important hyperparameters in Appendix H.5, robustness of L-STEP with different initial positional encoding input in Appendix H.6,
detailed reproducibility in Appendix I.
5.1. Experimental Settings
Datasets and baselines. We assess the ubility of L-STEP in performing link prediction with 13 datasets covering var- ious domains and collected by (Poursafaei et al., 2022); Wikipedia, Reddit, MOOC, LastFM, Enron, Social Evo., UCI. Flights, Can. Parl., US Legis., UN Trade, UN Vote, and Contact. Details about the dataset statistics are shown in Appendix G. We compare L-STEP with 8 state-of-the-art baselines, including JODIE (Kumar et al.. 2019), DyRep (Trivedi et al., 2019), TGAT (Xu et al., 2020), TGN (Rossi et al., 2020), CAWN (Wang et al., 2021b), TCL (Wang et al., 2021a), GraphMixer (Cong et al., 2023), DyGFormer (Yu et al., 2023), and FreeDyG (Tian et al., 2024). Across all 13 datasets, training/valiiaatooreettnng sets are follow- ing the standard library (Yu et al., 2023) by chronological splits with ratios 70%/155 (5%%1%% /15%. The large-scale datasets with pre-defined splits are publicly available at TGB Bench- mark (Gastinger et al., 2024)
5.2. Temporal Link Prediction Performance on 13 Classic Datasets
Due to the limited space, we present all baseline methods with respect to AP and AUC-ROC metrics with random negative sampling strategy here for the transductive setting in Table 1 and the inductive setting in Table 5 in Appendix H.I. The performance of historical and inductive negative sampling strategies both learning settings are placed in Appendix H.1 The first and second results are highlighted with Red and Blue. For the random negative sampling strategy. in Tables I and 5, L-STEP achieves competitive results over 13 datasets, outperforming most of the baselines with average rankings close to under both settings. More- over, the second-best results of L-STEP closely approach the corresponding best results by small gap. Notably, on some datasets, such as UN Trade, UN Vote, the difference between the second-best and L-STEP's performance is sub-
Evaluation metries and settings. Following existing works (Xu et al., 2020; Rossi et al., 2020; Yu et al., 2023) in evalu- ating models for link prediction, we assess L-STEP under two settings: transductive setting and inductive setting.
7

---

Learnable Spatial-Temporal Positional Encoding for Link Prediction
Table 2. Test MRR and Validation MRR in the worldwide leaderboard TGB benchmark
tgbl-review
tgbl-coin
Rank
Method
Test MRR
Validation MRR
Rank
Method
Test MRR
Validation MRR
GraphMixer
0.521 1 0.015
0.428 = 0.019
TNCN
0.762 1 0.004
0.740 1 0.002
L-STEP (Ours)
0.411 + 0.011
0.330 + 0.017
DyGFormer
0.752 + 0.004
0.730 + 0.002
TNCN
0.377 + 0.010
0.325 + 0.003
L-STEP (Ours)
0.711 + 0.0185
0.674 + 0.021
TGAT
0.355 = 0.012
0.324 = 0.006
TGN
0.586 + 0.037
0.607 0,014
5
TGN
0.349 + 0.020
0.313 = 0.012
EdgeBank (IW)
0.580
0.492
NAT
0.341 = 0.020
0.302 = 0.011
DyRep
0.452 + 0.046
0,512 0.014
DyGFormer
0.224 1 0.015
0.219 - 0.017
EdgeBank (unlimited)
0.359
0.315
8
DyRep
0.220 1: 0.030
0.216 = 0.031
CAWN
0.193 + 0.001
0.200 + 0.001
10
TCL
0.193 = 0.009
0.199 = 0.007
EdgeBank (tw)
0.025
0.024
12
EdgeBank (unlimited) 0.023
0.023
stantial, suggesting that L-STEP makes great improvements over existing methods. Regarding the historical and induc- tive sampling strategies, L-STEP also attains competitive results, as observed in Tables 6, 7, 8, and 9. In most cases, L-STEP surpasses the second-best by a substantial margin.
sentations at certain timestamp, and then obtain the link prediction between pair of nodes (u, v) time t. They typically start by concatenating the temporal representations of u, U at time I, and then process the concatenation with MLP layers to estimate the link occurrence probability, Usu- ally, the temporal representations of nodes are obtained by aggregating intrinsic node/edge features from recent tem- poral neighbors and interactions, which are then processed using more complex architectures.
5.3. Temporal Link Prediction Performance on the Large-Scale Benchmark TGB
In this section, we assess the scalability of our method by evaluating LTPT on lcage-scale temporal graphs from the TGB Benchmark (Gastinger al., 2024) with link predic- tion task. Specifically, we report L-STEP's performance rgbl-review and igbl-coin datasets in Table 2, following the given pre-defined splits and metrics. Moreover, rebl-review has 352,637 nodes and 4,873,540 edges, while igbl-coin has 638,486 nodes and 22,809,488 edges. As shown in Table 2, our method achieves competitive performance, ranking the 2nd place on rebl-review and the 3rd place on rgbl-coin 2, according the worldwide open leaderboard. To further demonstrate the efficiency of L-STEP, we provide runtime comparison between our method and some SOTA methods, DyGFormer (Yu et al., 2023) and FreeDyG (Tian et al., 2024), on US Legis and UN Trade datasets in Table 11 in Appendix H.3.
For example, TGN (Rossi et al., 2020) and JODIE (Kumar et al., 2019) employ the recurrent architecture, TGAT (Xu et al., 2020) utilizes the self-attention mechanism, DyRep (Trivedi et al., 2019) uses Temporal Point Processes, and more recently, GraphMixer (Cong al., 2023) leverages Mixer-MLP layers, while DyGFormer (Yu et al., 2023) har- nesses the power of transformers and FreeDDyG (Tian et al., 2024) utilizes Fourier Transform to encode neighborhood co- occurrence information. From another aspect, some meth- ods aggregate information from higher-order graph struc- tures. For example, TGN (Rossi et al., 2020) and TGAT (Xu et al., 2020) both aggregate information from k-hop neighborhoods, and CAWN (Wang et al., 2021b) samples random walks and encode them to derive the node repre- sentations. PINT (Souza et al., 2022) leverages positional features constructed from temporal random walks to en- hance the model's expressiveness. A detailed discussion and comparison between our method and PINT (Souza et al., 2022)'s 's positional features can be found Appendix F.
6. Related Work
Recently, many efforts have been made to develop the next- generation graph foundation models (Zheng et al., 2024a;b; Xu et al., 2024; Li et al., 2024; Wang et al., 2025; Zou et al., 2025). As an important pillar, current most temporal graph learning methods are designed to learn node temporal repre-
Our L-STEP achieves effectiveness with efficiency. First, our L-STEP only considers 1-hop neighborhood for in- formation aggregation and processes representations with simple MI.P transformations. More importantly, L-STEP integrates node and edge features along with evolving po- sitional encodings, which informative to support task out out-performacce... The integration is intuitive and does not really rely heavy attention mechanisms.
docs/
hnttos::/tgp..commeeedatat docs/ leader hintee__iiinkpppttttl-oooo
8

---

Learnable Tempioll Positional Encoding for Link Prediction
7. Conclusion
ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenRe- view.net, 2023. URL htt.tttts///ppeereeeee net//
In this paper, we propose a simple temporal link prediction model, L-STEP, which only relies on learnable positional encoding and MLPs to achieve out-performance over SOTA graph transformers in temporal link prediction tasks. In addi- tion to theoretical analysis of the effectiveness and efficiency, we design comprehensive experiments to demonstrate the empirical performance of L-STEP
pdFFiddcFFimbbiNNG
Dwivedi, V. P. and Bresson, X. A generalization of trans- former networks to graphs. CoRR, abs/2012.09699, 2020. URL https::///// /tap::://rrxiv http/vrxvvvv/// orq abs / 220...9992.. 09699.
Dwivedi, V., Luu, A. T., Laurent, T., Bengio, Y., and Bres- son, X. Graph neural networks with learnable structural and positional representations. In The Tenth Interna- tional Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL httpt:ttt///.. hatpss://pperreeee h/pp//ppppreeeeeeeeeeeeeeee net/ forum? id id-
Acknowledgments
This work is supported by National Science Foundation under Award No. IIS-2117902, and the U.S. Depart- ment of Homeland Security under Grant Award Number 17STQACC0001-08-000 The views and conclusions are those the authors and should not be interpreted as repre- senting the official policies of the funding agencies or the government.
Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Benchmarking graph neural networks. J. Mach. Learn. Res., 14:43:1-43:44 2023. URL http:
/ / //mmm...ooo wwt.ll.orgpppeer////ee/ee stspess/v4/22/ 0567. html.
Fu, D. and He, J. DPPIN: A biological repository of dy- namic protein-protein interaction network data. In IEEE International Conference on Big Data, 2022.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Fu, D., Zhou, D., and He, J. Local motif clustering on time-evolving graphs. In KDD, 2020.
Fu, D., Fang, L.,, Maciejewski, R., Torvik, V. I., and He,
J. Meta-learned metrics over multi-evolution temporal graphs. In KDD, 2022.
References
Ban, Y., Zou, J., Li, Z., Qi, Y., Fu, D., Kang, J., Tong, H., and He, J. Pagerank bandits for link prediction. In NeurlPS, 2024.
Fu, D., Zhou, D., Maciejewski, R., Croitoru, A., Boyd, M., and He, J. Fairness- tlique-preservvi spectral clustering of temporal graphs. In WWW, 2023.
Chen, J., Gao, K., Li, G., and He, K. Nagphormer: A tok- enized graph transformer for node classification in large graphs. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023, OpenReview.net, 2023. URL https: // oppereeview. wwwpaarwwwweei.eeeeeeeeeeeee htt.:/www....eeeeeeeeeeeee1e1100
Fu, D., Hua, Z., Xie, Y., Fang. J., Zhang, S., Sancak, K., Wu,
H., Malevich, A., He, J., and Long, B. Ver-graphormer: A mini-batch graph transformer via virtual connections. In ICLR, 2024.
Gastinger, J., Huang, S., Galkin, M., Loghmani, E., Parviz, A., Poursafaci, F., Danovitch, J., Rossi, E., Koutis, I. Stuckenschmidt, H., Rabbany, R., and Rabusseau, G. TGB 2.0: A benchmark for learning on tem- poral knowledge graphs and heterogeneous graphs. CoRR, abs/2406. 0bb/22406.09639, 2024. doi: 10.48550/ARXIV, 2406.09639. URL https: /td.dii..gg//oo//ooo 48855000500
Cong, W., Zhang, S., Kang, J., Yuan, B., Wu, H., Zhou, X., Tong, H., and Mahdavi, M. Do we really need compli- cated model architectures for temporal networks? In The Eleventh International Conference on Learning Repre- sentations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023, URL sattps://coet //pp://eeeeee.eeeeeemmm
Gupta, G. D., Coyaud, É.,, Gonçalves, J., Mojarad, B. A., Liu, Y., Wu, Q., Gheiratmand, L.,, Comartin, D., Tkach, J. M., Cheung, S. W., et al. A dynamic protein interac- tion landscape of the human centrosome-cilium interface. Cell, 163(6):1484 1499, 2015.
Daud, N. N., Ab Hamid, S. H., Saadoon, M., Sahran, F., and Anuar, N. Applications of link prediction social networks: A review. Journal of Network and Computer Applications, 166:102716, 2020.
Diao, C. and Loynd, R. Relational attention: Generalizing transformers for graph-structure tasks. In The Eleventh International Conference on Learning Representations,
He, X., Fu, D., Tong, H., Maciejewski, R., and He, J. Tem- poral heterogeneous graph generation with privacy, utility, and efficiency. In ICLR, 2025.

---

Learnable Spatial-Tempone Positional Encoding for Link Prediction
Huang, Z., Li, X., and Chen, H. Link prediction approach to collaborative filtering. In Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries, pp. 141-142, 2005.
Li, Z.,, Zheng, L.,, Jin, B., Fu, D., Jing, B., Ban, Y., He, J., and Han, J. Can graph neural networks learn language with extremely weak text supervision? CoRR, 2024.
Li, Z., Fu, D., Ai, M., and He, J. Apex2: Adaptive and ex- treme summarization for personalized knowledge graphs. In KDD, 2025a.
Kazemi, S. M., Goel, R., Jain, K., Kobyzev, I., Sethi, A., Forsyth, P., and Poupart, P. Representation learning for dynamic graphs: A survey. J. Mach. Learn. Res., 21:70:1- 70:73, 2020. URL http:// http://mllr.rrrppprrr//e/ v21/19-441 html.
Li, Z., Lin, X., Liu, Z., Zou, J., Wu, Z., Zheng, L., Fu, D., Zhu, Y., Hamann, H. F., Tong, H., and He, J. Language in the flow of time: umee-sriies-aiiees texts weaved into a unified temporal narrative. CoRR, 2025b.
Kim, J., Nguyen, D., Min, S., Cho, S., Lee, M., Lee, H., and Hong, S. Pure transformers are powerful graph learners. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Infor- mation Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022. 2022.
Lin, X., Liu, Z., Fu, D., Qiu, R., and Tong, H. Backtime: Backdoor attacks on multivariate time series forecasting. In NeurlPS, 2024.
Liu, Z., Qiu, R., Zeng. Z., Yoo, H., Zhou, D., Xu, Z., Zhu, Y., Weldemariam, K., He, J., and Tong, H. Class-imbalanced graph learning without class rebalancing. In ICML, 2024.
Kumar, A., Singh, S. S., Singh, K., and Biswas, B. Link prediction techniques, applications, and performance: A survey. Physica A: Statistical Mechanics and its Applica- tions, 553:124289, 2020.
Lu, L. and Zhou, T. Link prediction in complex networks: A survey, CoRR, abs/1010.0725, 2010. URL http: //arxiv. wwweiv..rggabb///0//
Martínez, V., Berzal, F., and Talavera, J. C. C. A survey of link prediction in complex networks. ACM Comput. Surv, 49(4))69:1-69:3) 2017. doi: 10. 10/1144/3012704 URL wwwphttpp//// doii orgiiiorrr1111 /10 10. 1145/3012704,
Kumar, S., Zhang, X., and Leskovec, J. Predicting dy- namic embedding trajectory in temporal interaction net- works. In Teredesai, A., Kumar, V., Li, Y., Rosales, R., Terzi, E., and Karypis, G. (eds.), Proceedings of the 25th ACM SIGKDD International Conference on Knowl- edge Discovery & Data Mining, KDD 2019, Anchor- age, AK, USA, August 4-8, 2019, pp. 1269-1278 ACM, 2019. doi: 10. 10.1145/32925000333333 33308955 URL https: //doi. //dpii.ogg/...111111 1001111443299 32925000 33300895.
Min, E., Chen, R., Bian, Y., Xu, T., Zhao, K., Huang, W., Zhao, P., Huang, J., Ananiadou, S., and Rong. Y. Transformer for graphs: An overview from architec- ture perspective. CoRR, abs/2202.00445. 2022. URL https: /aapss///axxivv http://///xcii.oooo///////00/// wttpgaas//22...0eeee2
Langley, P. Crafting papers on machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference on Machine Learning (ICMI,2000), pp. 1207-1216, Stan- ford, CA, 2000. Morgan Kaufmann.
Müller, L.., Galkin, M., Morris, C., and Rampásek, L. At- tending to graph transformers. CoRR, abs/2302.04181,
2023. doi: 1048550/ARXIV22322.01188 URL https: 11..///1.//
04181.
Le, D., Zhao, K., Wang, M., and Wu, Y. Graphlingo: Do- main knowledge exploration by synchronizing knowl- edge graphs and large language models. In 40th IEEE International Conference on Data Engineering. ICDE 2024, Utrecht, The Netherlands, May 13-16, 2024, pp- 5477-5480, IEEE, 2024a. doi: 10.1109/ICDE00146. 2024.00432. URL https: htt:://oiioooo http//dii.rgg//////////o 1109/ XCDE60146.20244 00432.
Poursafaci. F., Huang, S., Pelrine, K., and Rabbany, R. To- wards better evaluation for dynamic link prediction. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Infor- mation Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
Le, D., Zhong. S., Liu, Z., Xu, S., Chaudhary, V., Zhou, K., and Xu, Z. Knowledge graphs can be learned with just intersection features. In Forty-first International Confer- ence on Machine Learning. ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, net, 2024b. URL https: //openreview wwtp://wwwwwweweennneoeooea A115:mmyy:.-
Rampásek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for general, powerful, scal- able graph transformer. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
Li, Z., Fu, D., and He. J. Everything evolves in personalized pagerank, In www, 2023.
10

---

Learnable Temporlle Positional Encoding for Link Prediction
Rossi, E., Chamberlain, B., Frasca, F,, Eynard, D., Monti, E,, and Bronstein, M. M. Temporal graph net- works for deep learning dynamic graphs. CoRR, abs/2006.10637, 2020. URL abs 2006 6337.
Wang, L., Chang, X., Li, S., Chu, Y., Li, H., Zhang, W., He, X., Song, I.,, Zhou, J., and Yang, H. TCL. transformer- based dynamic graph modelling via contrastive learning. CoRR, abs/2105.07744, 2021a. URL https: //arxi/...ivvvi/i org/abs /taab//2105 2100. 07944.
Souza, A. H., Mesquita, D., Kaski, S., and Garg, V. Prov- ably expressive temporal graph networks. In Koyejo. S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans,
Wang. L.,, Hassani, K., Zhang, S., Fu, D., Yuan, B., Cong, W., Hua, Z., Wu, H., Yao, N., and Long, B. Learning graph quantized tokenizers. In ICLR, 2025.
Wang. Y., Chang, Y., Liu, Y., Leskovec, J., and Li, P. Inductive representation learning in temporal networks via causal anonymous walks. In 9th International Con- ference Learning Representations, ICLR 2021, Vir- tual Event, Austria, May 3-7, 2021. OpenReview.net, 2021b. URL https: htts::///pppeevieeeeee id=KYPZ4YsCPj
LA, USA, November 28- December 9, 2022, 2022.
Sundararajan, D. The discrete Fourier transform: theory, algorithms and applications. World Scientific, 2001.
Taylor, I. W., Linding, R., Warde-Farley, D., Liu, Y., Pesquita, C., Faria, D., Bull, S., Pawson, T., Morris, Q., and Wrana, J. L. Dynamic modularity in protein inter- action networks predicts breast cancer outcome. Nature biotechnology, 27(2):199-201 204, 2009.
Xu, D., Ruan, C., Körpeoglu, E., Kumar, S., and Achan, K. Inductive representation learning on temporal graphs. 8th International Conference on Learning Repre- sentations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https: / /openreview net fww.m?rrrmmmmmmm wwwoorrmmiirrrerrreeeee id=.Jddeeeyyiiii
Tian, Y., Qi. Y., and Guo, F. Freedyg: Frequency hanced continuous-time dynamic graph model for link prediction. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL https: //openrevies net feet/foorntt forum? i wdd.ddd2225m111
Xu, Z., Hassani, K., Zhang, S., Zeng, H., Yasunaga, M., Wang, L.,, Fu, D., Yao, N., Long, B., and Tong, H. Lan- guage models are graph learners. CoRR, 2024.
Tieu, K., Fu, D., Zhu, Y., Hamann, H. F., and He, Tempo- ral graph neural tangent kernel with graphon-guaranteed In NeurlPS, 2024.
Yu, L., Sun, L., Du, B., and Lv, W. Towards better dynamic graph learning: New architecture and unified library. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
Tieu, K., Fu, D., Wu, J., and Hc, J. Invariant link selector diitt-iiiitiittiion problem. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
for
Trivedi, R., Farajtabar, M., Biswal, P.,, and Zha, H. Dyrep: Learning representations over dynamic graphs. 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URLhttps:/ URL.tttss///peeeeeeee wptpr/eeeeeeeeeeeeeeeeeee net. formmoormmii www.miiiiieyyPeee.....
Zheng, L., Fu, D., Maciejewski, R., and He, J. Drgnn: Deep residual graph neural network with contrastive learning. Transactions on Machine Learning Research, 2024a.
Zheng, L., Jing, B., Li, Z., Zeng. Z., Wei, T., Ai, M., He, X., Liu, L., Fu, D., You, J., Tong, H., and He, J. Pyg-ssl: A graph self-supervised learning toolkit. CORR, 2024b.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin. I. Attention all you need. In Guyon, I., von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. V. N., and Garnett, R. (eds.). Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5998- 6008, 2017. URL neurips. http.//appppp/////aaat..
Zhong, S., Le, D., Liu, Z., Jiang, Z., Ye, A., Zhang, J., Yuan, J., Zhou, K., Xu, Z., Ma, J., Xu, S., Chaudhary, V., and Hu, X. Gnns also deserve editing, and they need it more than once. In Forty-first International Conference Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL https:/ // openreview net. / forum? ? Ic=
Zhou, D., Zheng, L., Fu, D., Han, J., and He, J. Mentorgnn: Deriving curriculum for pre-training gnns. In CIKM, 2022.
Absttraa..
html.

---

Learnable Spatial-Temporte Positional Encoding for Link Prediction
Zou, J., Fu, D., Chen, S., He, X., Li, Z., Zhu, Y., Han, J., and He, J. GTR: graph-table-rag for cross-table question answering. CoRR, 2025.
12

---

Learnable Spatial-Tempont Positional Encoding for Link Prediction
A. Appendix Contents
The appendix contains the following information:
Appendix B: Pseudo-code of L-STEP
Appendix C: Proof LPE
Appendix D: Elaborations on the Learnable Filter
Appendix E: Theoretical Time Complexity of L-STEP
Appendix Detailed Theoretical and Empirical Comparison with Provably Expressive Temporal Graph Networks
Appendix G: Dataset Details
Appendix H: More Experiments
Appendix H.1: The effectiveness comparison more learning and sampling settings
Appendix H.2: MLPs and Transformers performance on the proposed LPE positional encoding method
Appendix H.3: Running time comparison with SOTAs
Appendix H.4: LPE ablation studies wrt input node and edge features
Appendix H.5: Analysis of important hyperparameters
Appendix H.6: Robustness of L-STEP with different initial positional encoding input
Appendix I: Reproducibility of L-STEP
B. Pseudo-code for L-STEP
In this section, we provide the pseudo-code for L-STEP. Specifically, Algorithm. summarizes the computational process of the Lode-Link-PPsiitonna Encoder, Algorithm. 2 demonstrates the computation of the objective loss function, and finally, Algorithm. 3 briefly describe the training procedure of L-STEP as a neural architecture.
Algorithm Temporal Representation
Require: node u, time
Ensure: Temporal Representation for
{p%) Eq.
Pt +-1 Eq. 2
h +- Eq. 4
Hi Tu Eq. 5
ht h Eq. 5
h N + -.q.6 6
R + Eq. 7
hy, & Eq. 8
h + Eq.9 9
return h.
13

---

Learnable Temppalle Positional Encoding for Link Prediction
Algorithm 2 Loss Function
Require: positive samples, B negative samples
Ensure: L
Lip 0
Lpe
for i [1....,B B) do
h (pox) -- Algorithm. 1(u; (pos) t)
h (poa) +- Algorithm. 1(u 1(1
(pos) ()
h
(neg) f Algorithm. 1(2 ((ug
(nea) t)
h
Algorithm. 1(0 (neg) t) ((ffee))
(nea)
V1
(pos)
Eq. 10 with h ( h (20w))
y.
(neg)
t Eq. 10 with h"
(meg) h
Cip f- Cip + log(( (200))
+ (1 log (neg)
Cpe t Lpe lipt (pne))
P Po 112 aneg 1
(m)g) P (iag ll/
end for
Cip Lip (2B)
Lpe t- pp
C+ Eq. 13
Algorithm 3 Training Pipeline of L-STEP
Require: Data-loader over G, number of epochs (# Epochs)
Ensure: Link Predictions Initialize the PE of the initial snapshot with its Laplacian PE: p +- Laplacian PE of G for epoch in [1, ..... # Epochs] do
for (B positive samples, B negative samples) in Data-loader do
L < Algorithm. 2(B positive samples, B negative samples)
Back-propagate
for in [t,...., tg] do
if Finish link prediction time (1 E (n) then reveal new links and update positional encoding: Vu, pú, < -Eq. end if end for
end for end for
14

---

Learnable Spatial-Tempores Positional Encoding for Link Prediction
C. Proof of Theorem 4.1
start our proof for Eq. 14 by first stating the following Lemma about the eigenvalues of n-node ring graph, denoted by Ry
Lemma C.1. The real-valued part of the Fourier basis is the eigenvector of the Laplacian of the ring graph. Specifically, for n-node ring graph Ra, the k-th eigenvector of its Laplacian, L L(Rm), is
cos (- 0/n) cos(2x (2 1/n)
ring
ER"
(15)
cos (n 1))/n
and its corresponding eigenvalue is Xgng 2 cos(2xk/n))
Lemma. C.1 is motivated by Lemma 5.2.1 from the lecture Based on that, we can then extend to prove our Theorem. 4.1 as follows.
Proof. For short of notation, in the rest of this proof, suppose the positional encoding of snapshots at + 1 distinct timestamps before are denoted p"; p ..... pp, which are the Laplacian eigenvector of graph snapshots at to..... tt. and pt and PL. are denoted p p_+1 and p4+2 respectively. Again, for short of notation, omit the subscript in the positional encoding notations. In addition, denote L L(R,) the (un-normalized) Laplacian of n-node ring graph, Rn,
We start by giving the definition of "slow-changing" network. We suppose that our network is "slow-changing", in terms of graph topology, thus, we can assume the eigenvector of the Laplacian does not vary across timestamps, i.e., pd ss ... R p so now we focus on bounding the left-hand side of Eq. 14.
We start by considering the following equation:
a1
p171_
pu42 +
+ -z
+
-pp--p"
pd
p (
FW filter F-1
a1-1
=([p' p²
11
Jp² Dd p |+t
+ +(p' p²
pd1
p p
p -
a1
+ +/p" pz
p plll - p²]
FW filter
F-1
at-1
= -((p' - p² +p p
p' - p + pz
pir
p
p 1+l + +p¹ p''-1]
(16)
a1
+ [p pd 0 0
p L+ - p'] FW
filter
F-1
at-1
-([p' - 222 pb
pd p p p
- + pt p--1]
FW fitter F-1
=
p4
α1
= [p'
p' FW FW falter F-1
The eigen-decomposittion of L(Rz) is L(Rr) FAF-1, where A is diagonal matrix with the i-th entri is Xing Thus
15

---

Learnable Temppoal Positional Encoding for Link Prediction
a1
pp'
p"] F( falter
aL
α1
[p'
p"] FAF FW filter
F-1
(17)
aL
04
Ip' p"1 F(AW falter
F
aL
For simplicity, let W filter be a diagonal matrix, thus (A W fitter) is diagonal matrix. Therefore, we obtain
α1
[p'
p"]
F(AW filter F
(18)
= =pp
p41
AWWilter filter) F..
(F
1=1
aL
Thus,
p
p4+2 p ph ([p
pz 0
p1l - -p') -p]))FW FW
filter F-1 ...
04-1
=
p
pd
AAW filter (. F.F.F.
i=1
aL
W filter ):) Σ a,p')
(19)
p pl+1 pl+2 = -p- - -put1 - (1pp
p
p p -p'))FW filter
FW
0t-1
+ filter ) Σ azp')
==1
Therefore,
16

---

Learnable
Positional Encoding for Link Prediction
1p
p4t2112 S
(AW
filter )x(
asp") )l2
1
j=1
L
L ):
L
filter)
a,p')l
1l1 + 110
(AW
filler M)
Σ
a,p')) ) 1 + 11p" p11
(20)
1m1
1=0
L-1 Σ (L- -a
W filter
a
Ill
(AW yatter):))
1=0
where the first inequality holds due to the assumption of "slow-changing" network. For simplicity, we assume , 022,... 02-1 and the length of positional encoding p(() is normalized, i.e ai + :... :t..:t............. +0a-1 =
Thus,
(00) S (AWsuter)))) (2L - 2)
(21)
Since L < N, thus choosing small enough and choosing the filter such that Ele (AW f(tter) ) < 1 shows that the past positional encoding can be well approximation of the positional encoding the future snapshot.
D. Positional Encodings, Signals, and Noises Filtering
To start with, we pave the way for understanding our leamable filter by unraveling how positional encodings could be regarded as signals on graphs.
Let the Laplacian eigein-dewt decomposition of a graph snapshot G be L' = UAUT, Suppose G has n nodes, then U RR*x, where U's columns are G eigenvectors, and A diag(Aı, x2,..., An), where < ..... An. is a diagonal matrix consisting of L''s eigenvalues. In addition, let u, R be the 7thh eigenvector of L and its jth entry denoted as u.j then, the positional encoding of node i is defined p; = __....... u E IR.". In our case, the graph signal constructed by p. is calti-dimmesionall signal. It is noteworthy that our paper does not consider graph signal constructed by the eigenvectors, and thus our multi-dimensional signals formed by positional encodings, p., are not associated with signals yielded by cigenvalues Aç.
Next, we discuss the essence of using DFT and learnable filters to filer noises by elaborating what kinds of noises would be filtered by design. (1) First, it is the change is caused by randomness. To be more specifie, DFT is applied on the sequence of u's positional encodings at previous timestamps and the learnable filter is designed to filter noises across dimensions in the spectral domain. If the signal changes from high-frequency to low-frequency (or vice versa) over time by randomness, then the learnable filter filters out noise in the spectral domain of the sequence. (2) Second, it is the changes caused by entity activities. It is also notable that the change pattern may reflect the historical properties a batch of certain nodes, which is part of evidence for the current time decision making. Because our SimpleTLP updates positional encoding each timestamp as shown Eq. 3, this pattern will be recorded into the representation learning process constrained by the loss functions as shown in Eq. 11 and Eq. 12.
E. Theoretical time complexity comparison with SOTAs
Now, we give an in-depth analysis of the complexity of DyGFormer and FreeDyG as follows.
Suppose we are given E query links: {u4, 24 t As we move to new timestamps, new connections and new nodes will emerge, resulting in the changes in some nodes" neighborhoods; then, both L-STEP and DyGFormer need to update
17

---

Learnable
Positional Encoding for Link Prediction
historical neighbors for some nodes. (Note that for node, both L-STEP and DyGFormer consider its historical neighbors, so both methods would need perform an update if its neighborhood changes).
For each link (u,, Di f.), DyGFormer and FreeDyG first need to obtain the neighbor co- no-oceurrence information of the node pair (u,, uz) as follows. Suppose u, has p historical neighbors, a1..... : Gp. and ey has historical neighbors, bi...., bg. then the neighbor co-occurrence scheme of DyGFormer and FreeDyG requires counting (1) the number of times a1.-... Op are involved interactions with v; before time 4, and (2) the number of times b1 bi.... ... by are involved interactions with u, before time tç. In other words, for an arbitrary link (u,, 21, &4), the neighbor co-occurrence framework of DyGFormer and FreeDyG makes the computation of u, depend on vy 's information, as they have to count how many times historical neighbors of u, are also U3 historical neighbors, and vice versa. Thus, in order to make predictions for the aforementioned query links, DyGFormer and FreeDyG require at least (E) complexity.
On the other hand, for L-STEP, we first consider the unique nodes among Ui...., Ug, .I..... ug. Suppose there are n unique nodes, and let us denote them as cI...., Cn. then we could compute their temporal representation as stated in Eq. 9. Moreover, the process of obtaining the necessary components for Eq. 9, for any node cs, we only use e 'ss related information (most recent temporal neighbors links and its previous positional encoding). Thus, it takes L-STEP ((n) time compute the representation for these n nodes. To predict an arbitrary link (ui, 0y (4), we simply retrieve the representation for u, &2 that we just computed and apply Eq. 10
In summary, DyGFormer and FreeDyG have OEE) since they process a node pair (u, e)-reltted information, while L-STEP's complexity linearly scales with the number of nodes.
F. Detailed theoretical and empirical comparison with related works
In this section, we provide comparative discussion and experimental comparison between our method L-STEP and PINT (Souza et al., 2022), method for temporal link prediction that also leverages positional features.
To be more specific, PINT (Souza et al., 2022) proposes relative positional features that count the number of temporal walks of a given length between 2 nodes. As stated in PINT (Souza et al., 2022), temporal walks are defined as follows. An (L - ---nngh temporal walk is W = {[W]](()) (w2, t2), ..... (wz, tz)]. where f > f2 > ....ty tt and (w;-1, Wi, tz) is an interaction in the given temporal graph. In summary, PINT proposes a relative positional encoding that represents pair-wise node "distance" (here, the "distance" is the number of L-length temporal walks, assuming L is given). On the other hand, our L-STEP learnable positional encodings (LPH) fall into the category of global positional encodings, which encode the position of the node relative to the global structure of the graph.
Table 3. Performance comparison between PINT and L-STEP in transductive setting and inductive setting with random negative sampling
strategy
Dataset
Method
Transductive AP Transductive ROC-AUC
Inductive AP
Inductive ROC-AUC
PINT
81.60 + 0.67
84.50 + 0.60
67.01 2.76
70.41 2.34
Enron
L-STEP (Ours)
93.96 # 0.36
95.98 + 0.23
89.17 + 0.88
92.30 + 0.57
PINT
95.77 # 0.11
94.89 + 0.15
94.14 + 0.05
92.51 - 0.07
UCI
L-STEP (Ours)
96.67 + 0.47
97.62 + 0.23
94.60 0.41
95.88 0.17
Next, we present the empirical comparison between L-STEP and PINT (Souza et al., 2022) in Table 3. As shown in Table 3, our L-STEP outperforms PINT in all experimental settings (transductive and inductive). Regarding PINT's empirical evaluation, we adopt PINT's official implementation (via the GitHub link provided in the (Souza et al., 2022)) and use the exact hyperparameters presented in the PINT paper to reproduce their results on these datasets. Moreover, PINT (Souza et al., 2022) and L-STEP use the same data split.
G. Datasets
Here, in Table 4, we report a detailed regarding 13 datasets in our empirical assessment, which includes the domain, number of nodes, number of links, dimension of raw node and edge features. The statistics of Benchmark TGB are available at https: //tgb. eettb.ccomp..
hal.ll........oooo......a.....a. com/docs///ooooooooocccccccccccc inkprop/.
18

---

Learnable Spatial- Temporal Positional Encoding for Link Prediction
Table 4. Statistics of the datasets.
Datasets
Domains
#Nodes
#Links
#N&L Feat Bipartite
Duration
Unique Steps Time Granularity
Wikipedia
Social
9,227
157,474
& 172
True
month
152,757
Unix timestamps
Reddit
Social
10,984
672,447
& 172
True
1 month
669,065
Unix timestamps
MOOC
Interaction
7,144
411,749
& 4
True 17 months
345,600
Unix timestamps
LastFM
Interaction
1,980
1,293,103
&
True
1 month
1,283,614
Unix timestamps
Enron
Social
184
125,235
&
False
years
22,632
Unix timestamps
Social Evo.
Proximity
74
2,099,519
False
8 months
565,932
Unix timestamps
UCI
Social
1,899
59,835
&
False
196 days
58,911
Unix timestamps
Flights
Transport
13,169
1,927,145
- &
False
4 months
122
days
Can. Parl.
Politics
734
74,478
& 1
False
14 years
14
years congresses
US Legis.
Politics
225
60,396
& 1
False
12 congresses
12
UN Trade
Economics
255
507,497
& 1
False
32 years
32
years
UN Vote
Politics
201
1,035,742
&
False
72 years
72
years
Contact
Proximity
692
2,426,279
&
False
month
8.064
5 minntes
H. More experimental results
H.1. Empirical results for different negative sampling strategies
We provide empirical results for (1) random NSS for inductive setting in Table 5 (2) historical NSS for transductive setting in Table 6 and inductive setting in Table 7, (3) inductive NSS under transductive setting in Table 8 and inductive setting in Table 9.
Table 5. Performance Comparison in the inductive setting with random negative sampling strategy.
Metric
Datasets
JODIE
DyRep
TGAT
TGN
CAWN
TCL
GraphMixer
DyGFormer
Fre:DyG
L-STEP
Wikipodia
94.82 0.200 92.43
0.37
96.22
1 0.07
97.83
2 0.04
98.24 0.03
0.03
96.22
0.17
96.65 = 0.02 98.39 2 0.03 98.97 2 0.01 99.15 1 0.04
Reddit
96.50 0.13 96.09 1 0.11 97.09
1: 0.04 97.50 1 0.07 98.62
0.01 94,09 1 0.07 95.26 1 0.02 98.84 0.02 98.91
0.01 98.02
0.09
85,50
81.41
LastFM
81.61 :.82 83.02
+ 1.48 78.63
+ 0.31 81.45 : 4.29 89.42
73.53
1.66
82.11 : 0.42 94.23 1 0,09 94.89 1 0.01 96.25 : 0.43
Enron
80.72 1.39 74.55
1 3.95
67.05
1 1.51 77.94
1 1.02 86.35 1.5.
0,51
76.14
1 0.79
75.88
1 0.48 89.76 1 0.34 89.69 0.17 89.17 0.88
Social Evo.
91.96 1: 0.48 90.04
1: 0.47 91.41
1. 0.16 90.77
0.86 79.94
0.18 91.55
0.09
91.86
1: 0.06 93.14
0.04 94.76 0,05 91.71 0.32
79.54
92.73
87,36
94.54 94,85
AP
Flights
94.74 0.37 92.88
1. 0.73 88.73
1. 0.33 95.03
0.60
97.06
0.00 83.41
1 0.07
83.03
1 0.05 97.79 1 0.02 96.42
16642.10.30 97.43 0.15
Can. Parl.
53.92 4: 0.94 54,02
1: 0.76 55.18
1: 0.79 54.10
0.93
55,80
0.69
54.30
0.66 55.91
1: 0,82 87.74 0.71 52.96 :: 1.05 92.25 0.24
US Legis.
54.93 1:::::220 57.28
1: 0.71 51.00
1: 3.11 58.63
0.37
53.17
1.20 $2.59 1 0.97 50.71
1: 0,76 54.28 2.87.888777 53.05
2.59
61.98 1.31
Trude
61.03
58.31
0.12 62.17
2.01
UN Vote
56.64 0.96 54,62
2:22
52.24
+: 1.46
58.85
2,51
49.94
0.45
51.60
50.68
0.44
55.93
0.39
50.51
1.02
75.09 4: 0.34
Contact
94.34:1:.. 92.18
0:41 95.87
1: 0.11 93.82
1: 0.99
89.55
1:
0,30
91.11
1: 0.12 90.39
1: 0.05 98.03 : 0.02
97.66
1 0.04
97.25 1: 0.07
Avg. Rank
6.38
7.54
7.08
5.31
5.38
7.54
6.92
2.62
4.15
2,08
Wikipedia
9.223
0.45
95.90
97.72
0.04
96.30
98.48
99.30
Reddit
0.13 96.05
0.12 96.98
97.39
98.42
0.02
93.80
0.07
94.97
98.71
0.01
98.84
0.01 98.49
0.06
MOOC
83,16 84.03
0.49 86.84
91.24
0.9
81.86
- 0.25 81,43
0.19
82.77
0.24 87 6
0,51
87.01
0.74
90.63
0.21
LasFM
11.13+3..3 82.24 1.51 76.99 0.29
82.61
3,15
87.82
+ 0.12 70.84
0.85
80.37 + 0.18 94088
0.08
94.32
0.03
97.66 0.21
Enron
81.96 76.34
64.63
78.83
87.02
07.02
72.33
0.99
76.51 0.71 90.69
0.25
92.30
Social Evo.
0.29
9.418
93.41
0.59
022
0.18
94.09
95.29
96.1
94,09 0.24
UCT
78.80 +.094 58.08 +-8
77.64
0.38
86.68
2.29
90.40
+.11
84.49
1.82 89.30
0.57 92 4.13
93,01
0.08
95.88 0.17
ROC-AUC
Flights
95.21 +: 0.32 93.56
88.64
0.3
95.92
043
0686
82.48
0.01 82.27 0.06 97.80 -
96.0
0.29
98.46
0.07
Can. Parl.
53.81 + 1.14
55.27
56.51
55.86
5883
55,83
1.07 58.32 1.00
52.89
95,06 0.11
US Legis.
58.12 +.35 6
48.27
3.50
62.38
0.48
$1.49
1.13
50.43
1.48 47.20
53.21
53.01
3.14
66.18
1.19
UN Trade
62.28 + 0.50
62.72
0.12 59.99
3.50
67.05
0,21
63.76
0.07
63.48
0.37
67.25
83.95 + 1.76
UN Vote
58.13 + 1.43
51.83
1.35
61.23
2.71
48.34
50,51
= 1.05
50.04
0.86
56.73
7.
49.97
1.22
82.01 0.21
Contact
95.37 0.92
0.38
96.53
+
94.84
0.34
93.05
0.09
92.8
98.30
0.02
98.11
0.02
0.07 1.54
Rank
6.38
7.54
3.71
19

---

Learnable Spatial-Tempordl Positional Encoding for Link Prediction
Table 6. Performance comparison in the transductive setting with historical negative sampling strutegy.
Metric
Datasets
DyRep
TGAT
TGN
CAWN
GrahiMixer
DyGFormer
FreeDyG
T-STEP
Wikipedia
83.01 + 0.66 79.93 + 0.56
87.38
0.22
86.86
0.33
71.21
+ 1.67
89.05
= 0.39 90.90
2.54
91.39 + 0.57
99.10 0.5T
Reddit
80.03 + 0.36 0
79.55
81,22
80.82
+ 0.45
77.14
7.14
08.4 81,57 + 0.67
85.67 + 1,01
93.25 = 1.13
MOOC
78.94 + 1.25 75.60
1.12 82.19
0.62
87.06
1,93
74.05
+ 0.95
77.06
+ 0.41 71.77 + 0,92 8585
0.66
86.71 + 0.81
96.52 + 1.58
LastFM
74.35
74.92
71.59
+1.99+0.22
7688
4.64
86
+ 0.43
59.30
2.11 72.47
81.57
0.48
79.71
94,88 +
Enron
69.85 1: 2.70 2.76
64.77
1,05 73,91
1. 1,76 64.73
1 0.36 70.66
1 0.39 77.98
1.98 75.63 1 0.73
78.87
1 0.82
95.42 1 0.53
Social Evo.
87.44 + 6.78 93.29 +
0.43
95.01
+ 0.44 94.45
0.56 85.53
+ 0.38 94.74
0,31 94,91
0.31 97.38
+ 0.14
97.79
+ 0.23
90.19 + 2.01
UCI
75.24 5.80 13.10:1..11
68.27
1 1.37 80.43
1: 2.12 65.30
1 0.43 80.25
2.74 84.11
1,35
82.17
0.82
86.10 1 1.19
80.76
1: 1.88
AP
Flights
66.48
67.61
72.38
0.18
64.72
0.97 70.68
0.24
71.47
66.59
0.49
66.13
82.02
Can. Parl.
51.79 1: 0.63 63.31
67.13
0.4
66.53
1: 2.77 65.93
74.34
0.87
97.00
0.31
72.22
+ 2.47
75.03 1: 1.76
US Legis.
51.71 1: 5.76 86.88 1 2.25
62.14
6.60
74.00 7.57 68.82
1 8:23
80.53
3.95
81.65
1.02
85.30
3,88
69.94 1 0.59
62.66 1. 3.54
UN Trade
61.39 = 1.83 59.19
55.74
0.91
5.54
55.71
+ 0.38
55.90
1.17
57.05
1.22 64.41
1.40
80.00 + 1.55
UN Vote
70.02
69.30
52.96
51.26
52.30
51.20
5U.61
61.43
Contact
95.31 + 2.13 96.39
96.05
0.52
93.05
+ 2.35
84.16
+ 0.49
93.86
0.21
93.36
0.41
97,57
+ 0.06
97.32 + 0,48
80.24 + 1.98
Avg. Rank
6.62
6.0
6.31
4.85
8.62
6.62
5.08
3.38
4,23
3.31
Wikipedia
80.77 1: 0.73 77.74 1 0.33
82.87
0.22
82.74
0.32 67.84
1 0.64 85.76
0.46
87.68
0.17
78.80
1: 1.95
82.78 1 0.30
99.21
1: 0.48
Reddit
80.52 80.15
0.16
0.19 80.27
:
0.16
71.80
80.54
0.29
85.92
+
%6.40 0.59
MOOC
82.75 0.83 81.06
0.94 80.81
= 0.67 88.00
1.80 71.57
+ 1.07
72.09
76.68
= 1,40
87.04
88.32 +: 0.99
97.69 + 0.94
LastFM
75.22 2.36 74.65
+ 1.98
(4
0.26 77.97
+ 3.04
83 + 0.24
47.24
3.13
64.21
0.35 = 0.73 78.78
73.53 + 0.12
97.66 + 1.96
Enron
75.39 2.37
3.56
61.8
1.43 77.09 + 2.22 65.10
0.88
75.27
= 1.14 76.55
0.52
75.74
0.72
95.79 + 0.33
Social Evo.
90.06 3.15 93.12
93.08
+ 0.59 94.71
0.53 87.43
93.44
0.68
94.39
+ 0.31 97.28
0.07
97.42 + 0.02
93.60 + 2.27
UCI
78.64 3.50 57,91
58.89
1.57
2.68 57
86
0.15
72.25
77.54
2,02 76.97
80.38 + 0.26
90.59 + 1.60
ROC-AUC
Flights
68.97 +: 1.87 69.43
+ 0,90 72.20
0.16
68.
0.95
66.
+ 0.71
70.57
-
70.37
+ 0.23 68.09
0.43
67.83
+ 1.46
92.84 +: 1.21
Can. Parl.
62.44
70.16
1,70
70.86
0,94
73.23
3.08
72.06
69.95
79.03
+ 1.01 97.61
0.40
77.59
+ 6.22
+ 87,22
US Legis.
67.47 1 6.40 91.44
1 1188 73.47
5.25
83.53
1 4.53 78.62
7.46
83.97
3.71 85.17
0.70 90,77
1.96
63.49
13.04
76.64 3.38
UN Trade
68.92 + 1.40 64.36
+
1.40
60.37
0.68
63.93
+ 5.41
63.09
+ 0.74
61.43
+ 1.04
63.20
1.54 73,86
1.13
87.67 + 1.80
UN Vote
76.84 1 1.01 74.72
1: 1.43 $3.95
3.15
73,40
1: 5.20
51.27
1 0.33
$2.29
1: 2.39
52.61
1: 1.44 64.27
1: 1.78
52.76
1: 2.85
72.92 1 1.73
Contact
96.35
96.00
95.39
0.43
93.76
1.29
83.06
93.34
93.14
0.05
97.12
90,99
Avg. Rank
5.38
3.69
6,92
4.31
8.54
7.15
5.69
3.69
4.92
2.69
Table 7. Performance comparison in the inductivv setting with historical negative sampling strategy.
Metric
Datasets
JODIE
DyRep
TGAT
TGN
CAWN
TCL.
GraphMixer
DyGFurmer
FreeDyG
L.STEP
Wikipedia
68.69 + 0.39 62,18 + 1.27 84.17
0.22 81.76
0.32
67.27
1.63
1.63 82.20
+ 2.18 87.60 + 0.30 71.42 + 4,43 82.78 +0,30 98.45 + 0.88
Reddit
62.34 62.34:00.54
61.60 0.72 63.47
0.36
64.85
+ 0.85 63.67
0.4 60.83
+ 0.25 64.50
+ 0,26 66.37 + 0.60 66.02 +: 0.41 85.74
2.46
MOOC
63.22
6.293:1+224
76.73
77.07
3.41 74.68
- 00.68
74.27
74.00
= 0,97 80.82
0.30 81.63
81.63
0.33 95.17 2.78
LasFFM
71.45 76.27
0.25
66.65
+.11
0.43
66.78
+ 0.65 76.42
+ 0.22 76.35
77.28
1-28440.2 0.21 92.96 + 1.08
Enron
65.86 22.08
61.40
1.31
62.91
6,,70
67.11
0.62
72.37
67.07
0.62
73,01
+: 0,88 89.37 + 1.01
Social Evo.
88.51 0.87 8.07
93.97
0.4 90.66
100661102
1.62
0.88
94.10
0.31 94.01
0.47
0.16
96.69
85.13 + 1.05
63.11 52.47
70.52
00522+0999
70.78
64.54
76.71
81.66
0.49
72
82.3
0.39
75.97
AP
Flights
61.01
6.1 0.37
59.31
057
64.50
65.28
57.11
56.72
1.30
71.54 + 2.12
Can. Parl.
0.88
52.28
06472
54.42
0,014
55.71
0,74
55.84
0.73 87.40
0.81
68.91 = 1.63
US Legis.
2.11 62.10
141
51.83
+.95
61.18
1,10
55.56
1.71
53.87
+ 1.41
52.03
+ 1.02
56.31
3.46
53.63
4.38
49.51 + 1.09
UN Trade
55.46 1.19 0.84
55.28
52.80
3,19 55.00
55.76
1.03
54.94
0.97 53.20
1.07
79.09 + 1.86
UN Vote
61.04 1.30 60.22
1.78 53.05
+ 3.10
63.74
3,00
47.98
0.84
54.19
2.17 48.09
0.43 52.63
1.633-1..26
1,26
50.23
1.65
61.89 1.28
Contact
90.42 2.34 89.22
+ 0.66
94.15
+ 0.45
88.13
+ 1.50
74.20
0,80
90.44
+ 0.17
89.91
+ 0.36 93.56
+ 0.52
93.26
1.42
79.08 + 2.24
Avg. Rank
6.85
6.85
5,31
5.85
7.54
3.23
4.92
4.38
4.77
3.31
Wikipodia
61.86
0.53 57.54
: 1.09 78.38
: 0.20
75.75
0.29
62.04
0.65
79.79 = 0.96
82.87
= 0.21 68.33 - 2.82
82.08
0.32
98.59 : 0.82
Reddit
61.69
0.37
64.43
0,27 64.55
0.50
64,94
64.27
64.81
0,31
92.04 1.87
MOOC
64.48 1.64 64,23 1 1.29
74,08
1 0.27
77.69
3,55 71.68
0,94
69.82
0.32
72.53
0.84
80.77
0.63
81.52 1 0.37
96.85 1. 1.59
LastFM
3.244
1
69.89
0.28 66.99
67.69
55.8
1.85 70.07
0.20 00.73
7263
0.16
96.34 :: 1.68
Enron
65.32 2.50
57.84
11 62.68
1.09
62.25
64.06
68.
65.78
70.09
0.65 92.14 0.70
Social
88.53
87.93
0.772
92.10
93.28
93.62
96.91
96.9
90.08
ROC-AUC
UCI
60.24
51.25
2.33
62.32
62.69
0.0
0,10
70.46
75.98
65.55
76.01
0.75 84.63 :: 1.23
Flights
60.72.1:1 1.29 61.99
63.38
0.26
59.66
1.04
56.58
1
0.44
63.48
0.23
63.30
56.5
55.20
85.60 1 1.47
Can. Parl.
51.62 - 1.00
58,30
55.64
60.11
048
57.30
1.03
56.68
8868
51.20
1.99
80.73 + 1.09
US Legis.
58.12 14.12:22.94 67.94
49,99
64.87
1311
52.12
2.13
49.28
56.7
5,92
55.74
UN Trade
58.73 1.19 57.90
1 1.33
59.74
1 0.59
55.61
3.54
60.95
0.80
61.12
0.97
59.88
1 1.17 58.46
1.65
86.26 1. 1.78
UN Vote
65.16 + 1.28
63.98
+ 2.12
51.73
+ 4.12
68.59
3.11
48.01
1.77
$4.66
= 2.11 45.49
+ 0.42
53.85
2.02
48
2.44
72.98
:: 1.22
Contact
90.80 +: 1.18 88.88
1: 0.68
93.76
4 0.41
88.84
+: 1.39
74.79
0.37
90.37
2 0.16
90.04
= 0.29
94.14
4
0.26
94.27
0.77
88.69
1: 2.24
Avg. Rank
6.54
7.46
5.92
7.08
5.54
4.38
4.62
2.46
20

---

Learnable Spatial-Tempone Positional Encoding for Link Prediction
Table 8. Performance comparison in the trunsductive setting with inductive negative sampling strategy.
Metric
Datasets
JODEB
DyRep
TGAT
TGN
CAWN
TCL
GraphMixer
DyGroemer
FreeDyG
L-STEP
Wikapedia
75.65 1. 0.79 70.21
1.58
87.00
1 0.16
85.62
1 0.44
74.06
2.62
86.76
0.72
88.59 1 0.17 78.29 1 5.38 90.05 1 0.79 98.66 1 0.94
Reddit
86.98 0.016
0.26 89.59
88.10
91.67
0.24
87,45
0.29 85.26
91.11
0.40 90.74
0.17 98.15
MOOC
65,23 2.119 61,66
0.95 75.95
1: 0.64 77.50
1 2.91 73,51 1 0,94
74.65
1 0.54
74.27 1 0.92 81.24 0,69 83.01
0.87
97.49 1: 0.99
LasFM
62.67 1.49 64.41 2,70 71.13
1 0.17 65.95
1 5.98
67.48
1 0,77 58.21
1 0.89 68.12 1 0.33 73.97 1 0.50 72.19 1 0.24 93.92 1 1.10
Enron
68.96 0-66++0.90 0.98 67.79 + 1.53 63.94
+ 1.36 70.89
+ 2.72
75.15
0.58
71.29
+ 0.32 75.01
+ 0.79 77.41 + 0.89 77.81
0.65 98.98
+ 0.53
Social
89.82 4.11 93.28
0.48 94.84
95.13
0.56 88.32
94,90
0.36 94.72 1: 97.68
97.57
0.15 90.53
1:
UCT
65.99 1.40 54,79 1,76 68.67
1: 0.84 70.94
0.71 64.61
0,48
76.01
1,11 80.10
0.51 72.25 1 1,71 82.35
0.73 74.08
1 1,84
AP
Flights
69.07 4.02 70.57 + 1.82 75.48
+ 0.26 71.09
+ 2.72
69.18
+ 1.52
74.62
+ 0.18 74.87
+ 0.21 70.92
+ 1,78 65.56
+ 1.10
80.75
+ 1.51
Can. Purl.
48.42 0.66 58.61 1. 0.86 68.82
1: 1.21 65.34
1. 2.87
67.75
1.00
65.85
1 1.75 69.48
1 0.63 95.44
1 0.57 59.83
5.15 73.79 1 1.26
US Legis.
50.27 5.13
61,91
67.57
65.81
8.52
78.15
79.63
81.25
3.62
5.36
57.67 1.
UN Trade
60.42 + 1.48 60.19 + 1.24 60.61
+ 1.24 61.04
6.01
62.54
0.67
61.06
1.74
60.
+ 1.29 55.79
1.02
80.96 + 1.12
UN Vote
67.79 1. 1.46 67.53
1 1.9%
52.89
1 1.61 67.63
1. 2.67
52.19
1. 0.34
50.62
1 0.82
$1.60
1 0.73
51.91 11 0.84
51.14
1 1.56
59.42 1 3.73
Contact
93.43 +: 1.78 94.18 4 0.10 94,35
1: 0.48 90.18
+: 3,28
89.31
0.27
91.35
4: 0.21 90.87
4 0.35
94.75
0.28
94.89
80.15 4: 1.48 0.89
Avg. Rank
7.69
7:23
5.38
6,46
5.69
3.92
4.85
3.31
Wikipedia
70.96 0.78 67.36 + 0.96
81.93
+ 0.22 80.97
0.31
70.95
82, +
0.48 84.28
75.09
3.70
82.74
0.32
98.78 + 0.91
Reddit
83.51 0.15 82.90
0.31 87.13
+ 0.20 84.56
+ 0.24
88.04
0.29
84.67
= 0.29 82.21
= 0.13
86.23
0.51
84.38
0.21
98.51 + 0.40
MOOC
66.63 2.30 63.26 + 1.01 73.18
+ 0.33 77.44
+ 2.86
70.32
+
143
70.36
+ 0.37 72.45
+: 0.72
80.76
0.76
78.47
+ 0.94
98.31 0.59
LastF
6..42
2.11 63.99
0221
65.46
67.92
0.4
46.93
2.59 60.22
0002
69.26
72.30
0.59 97.08 1.47
Enren
70.92
6.44
60.45
71.34
15.17
67.64
0.85
74.07
77.27
95.79
Social Evo.
90.01 +.119
0.38
92.94
0,55
89,93
93.44
+ 0.72 94.22
0.32 97.51
01.11:00.000
9844
93.73 2:22
UCI
1.244:11.26
54.25
1..5522000
6.080
64.11
1.04
0.26
70.05
1.86 74.59
66.96
75.39
84.09 + 1.61
ROC-AUC
Flights
69.99 3.10 1.55
73.47
0.18
71.63
0.75
72.54
0.19 72.21
69.3
0.55
92.32 1.51
Can. Parl.
52.88 0.80 63.53
72.47
+ 1.18 69.57
72,93
69.47
2.12 70.52
96.70
66.58
85,80 1.51
US Legis.
59.05 5.55 0,74
71.62
5:42
78.12
76.45
82.54 = 3,91 84.22
=
87.96
1.80
60.71
9.72
70,81 3.72
UN Trade
66.82 + 1.27 65.60
+ 1.28 66.13
+ 0.78
66.37
+ 5.39
0.74
67 = 1.21 66.33
= + 1.64 51.89
1,223666222226
62.56
87,92 1 1.61
UN Vote
73.73 + 161 72.80
+: 2.16
53.04
+ 2.58
72.69
+ 3,72
52.75
0
$2.02
+ 0.74
53.37
1.26
51.95
70.70
3,58
Contact
94.47 1.0
94.23
0.18
94.10
0.41 91.64
1.72
87.68
0.24 91.23
0.19
90.96 0.27 95.01
0.15
95.41
=
0.49
90.68 + 1.59
Avg. Rank
6.92
7.0
5.85
5.23
6,23
5.92
5.69
4.23
5.15
2.77
Table 9. Performance comparison in the inductive setting with inductive negative sampling strategy.
Metric
Datasets
JODIE
DyRep
TGAT
TGN
CAWN
TCL
GrapMMixer
DyGFommer
FreeDyG
L-STEP
Wikipedia
68.70 1: 0.39 62.19 1: 1.28
84.17
1 0.22
81.77 1: 0.32
67.24
1.63
82.20
1: 2.18 87.60 1 0.29 71.42 1: 4,43 87.54 a: 0.26 98.45
0.8%
Reddit
62.32
61.58
= 0.72 63.40
: 0.36
64,84
63
60.81
0.26 64.49
0.25 65.35 0.60 64,98 - 0.20
85.76
MOOC
63.22:1.555
62.92
76.72
0,30
77.07
3.40
74.69
1.68
74.28
0.53 73,99
80.82
0.30
81.41
1 2.78
LasiPM
70.39
71.45 +: 1.75 76.28
108.1.022 0.25 69.4
4.65
0.47
65.78
0.65 76.42
76.35
0.52 77.01
1 0.43 92,96
1.08
Fnron
65.86 4.3.1 62,08 + 2.27 61.40
1.30 62.00
1.16
67.11 + 0.62 72,37 1.38 67.07 + 0.62 72.85
+ 0.81 89.36 + 1.01
Social Evo.
88.51 0.87 88.72 +: 1.10 93.97
0.54
03
0
9.47
96.82 1: 0.17 96.91 : 0.12 85.13 1 1.05
UCI
63.16 52.47 1: 2.09 70.49
1 0.93
70.73
70.73
(4.54
64.54
76.65 1: 0,99 81.44
72.13 1: 1.86 82.06
: 0.58 75.97
1: 1.13
ind
Flights
61.01 +- 1.66
64.72
0.37 59.32
56.8
64.50
66.29
57.11
0.20 56.70
69.14
Can. Purl.
52.24
0.28 56.46
16446+00000
54.18
57.06
55.66
55.76
87.22
0.82 52,33
0.87 69.59 1.45
US Legis.
52.94 2.11 62,10
1.41 51.83
1. 3,95
61.18
1: 1.10
55.56
1.71
53.87
1.41
$2.03
1.02 56.31
1 3.46
53.63
1 4.38
49.51 1: 1.09
UN Trade
55.43 +: 1.20 55.42
+ 0.87
55.58
+ 0.68
52.80
+ 3.24 54.97
0.38
55.66
+: 0.98
54.88
+ 1.01 52.56
4: 1.70
79.12 +: 1.84
UN Vote
61.17 + 1.33 60.29 + 1.79
53.08
+ 3.10 63,71
+- 2.97 48.01
0:82
0.2
54.13
+ 2.16
48
10
+ 0.40
52.61
1.25
50.21
+ 1.74
61.88
+: 1.27
Contact
90.43 2.33 89.22 + 0.65
2.33
94.14
0.45
88.12
- 1,50 74.19
0.81
90.43
+ 0.17 89,91
+ 0.36
93.55
0.52
93.26
- 1.41
79.09 + 1.25
Avg. Rank
7.08
5.23
5.77
7.54
5.23
4.46
3.31
Wikipedia
61.87
0.53 57.54
1.09
78.38
0.20
75.76
62.02
0.65
79.79
0.96 82.88
0.21 68.33
2.82
83.17
: 98.59 0.82
Reddit
61.69 0.39 60.44
0.37 64.39
1: 0.27 64.55
0.50
64,91
0.21 61.36
0,26 64.27
1 0.13
64.80
0,25 64.51
1: 0.19 92.05 :: 1.87
MOOC
64.48 1: 1.64
64.22
1: 1.29 74.07 1: 0.27 77.68
:: 3.55
71.69
0.94
69.83
1: 0,32
72.52
1 0.84
80.77
1 0.63
75.81
1: 0.69
96.85 1: 1.59
LastFM
68.44
68.79
1.08 69.89
+ 0.28 5 67.68 1
55.88
1.85 70.07
0.20 70.73
0 0,37 71.42
- 0,33 96.34 : 1.68
Enron
15.32:1:.57
61.50
57.83
2.18 62.68
62.27
64.05
1.02 68.
65.79
: 68.79
- 0,91 92.14 0.70
Social Evo.
91.88
0.72 92.10
83,54
93.28
93
96.91
96.79
90.08 3.91
UCI
60.27 +- 1.94 51.26 + 2:40 62.29
1.17 62.66
56.39
70.42
75.97
65.58
1.00
73.41
+ 0.88
84.63
1.22
ind
Flights
60:72 :: 1.29 61.99
1.39 63.40
0.26
59.66
1.05
56.58
1.44
63,49
63.32
56.05
0:
0.22
55.18
-: 1.04
83,87
: 1.30
Can. Parl.
51.61 1: 0.98 52.35 0.52 58.15
0.62
55.43
0.42
60.01
0.47
56.88
1858881000
0,93
56.63
1.09
88.51
1 0.73
51.37
11 2:23
81.26
1: 3.92
US Legis.
58.12 +: 2.94 67.94 +: 0.98 49.99
488
64.87
1.65
54.41
1,31
52.12
+ 2.13
49.28
0.86
$6.57
3.22
53.75
+ 5.92
55.74
+: 1.53
UN Trade
58.71 + 1.20 57.87
+ 1,36 59.98
0.59
55.62
+: 3.59
60.88
0.79
61.01
0.93
59.71
+ 1.17 57.28
3.06
86.28
1.76
UN Vote
65.29 1 1,30 64.10
2.10 51.78
4.14
68.58
48.04
1.76
$4.65
2.20
45.57
0.41
53.87
2.01
48.93
1:
72.98
1.22
Contact
90.80 1 1.18 88.87
1: 0.67
93.76
0.40
88.85
à: 1.39 74.79
0.38
90.37
1 0.16
90.04
1 0.29
94.14
0.26
94.27
à: 0.76
88.69
3.25
Avg. Rank
6.54
7.38
5.69
5.77
7.0
5.54
5.31
4.23
5.08
2,46
21

---

Learnable Spatial-Temporal Positional Encoding for Link Prediction
H.2. Demonstrating the MIPs and Transformers on the proposed LPE positional encoding
Here, we empirically show that simple architectures like MLPs can fully harness our learnable positional encoding finish temporal link prediction tasks.
By performing an ablation study of using Transformers (instead of MLPs) to help L-STEP learn positional encodings, as shown in Table 10, we can discern (1) in most cases (i.e., 9 of 13 datasets), our vanilla L-STEP can outperform, and the gain is not marginal; (2) in a few cases, adding the attention mechanism on L-STEP to replace MLPs can boost the performance to a small extent, and it is prone to cost more computational memory, like OOM in the Flights dataset.
Table 10. Comparison of replacing MLPs in L-STEP with Transformers.
Dataset
Method
Transductive AP
Transductive ROC-AUC
Inductive AP Inductive ROC-AUC
STEE + Attention
98.50 0.73
98.85 = 0.50
98.11
0.83
98.49 + 0.62
Wikipedia
L-STEP
99.34 + 0.04
99.48 0.03
99.15 0.04
99.30 + 0.03
L-STEP Attention
98.90 0.10
99.13 0,08
97.75 0.26
98.29 = 0.16
Reddit
L-STEP
99.37 0.04
99.49 = 0.03
98.02 0.09
98,49 + 0.06
I-STEP + Attention
82.46 + 3.61
85.38 2.93
82.57 + 4.24
85.80 + 3.18
MOOC
L-STEP
86.94 +: 0.34
89.28 0.28
88.49 0.24
90.63 = 0.21
LTSPPP+ + Attention
95.50 0.70
97.19 0.50
96.07 0.36
97.62 0.25
LastFM
L-STEP
96.06 0.30
97.52 0.17
96.25 0.43
97.66 + 0.21
L-STEP + Attention
92.56 + 0.53
95.02 0.33
86.41 1.15
90.70 = 0.72
Enron
L-STEP
93.96 0.36
95.98 0.23
89.17 0.88
92.30 = 0.57
L-STEP + Attention
90.26 0.69
92.61 0.58
90.75 0.31
93.50 + 0.30
SocialEvo
L-STEP
92,22 + 0.25
94.33 0.21
91.71 + 0.32
94.09 + 0.24
LTST + Attention
96.06 0.53
97.12 0.41
93.00 1.30
94.59 + 0.85
UCI
L-STEP
96.67 0.47
97.62 0.23
94.60 0.41
95.88 + 0.17
L-STEP+ + Attention
OOM
OOM
0OM
0OM 98.46 + 0.07
Flights
L-STEP
98.94 + 0.10
99.38 0.04
97.43 = 0.15
L-STEP + Attention
98.36 0.12
99.01 0.07
92.59 0.32
95.37 + 0.25
Can. Parl.
L-STEP
98.24 0.11
98.97 0.06
92.254 0.24
95.06 + 0.11
L-STEP + Attention
76.84 + 0.61
84.16 0.40
64.07 1.31
68.13 = 1.78
US Legis.
L-STEP
76.74 0.60
83.89 0.43
61.98 1.31
66.18 = 1.19
L-STEP + Attention
77.45 3.27
83,94 2.23
79,83 3.28
85,95 + 2.13
UN Trade.
L-STEP
75.84 + 2.08
83.17 = 1.28
76,80 = 2.01
83.95 + 1.76
L-STEP Attention
74.65 0.46
80.73 0.40
76.10 0.88
82.89 1 0.64
UN Vote
L-STEP
73.40
79.59 = 0.02
75.09 0.34
82.01 1 0.21
L-STEP + Attention
97.32 + 0.15
98.12 = 0.10
96.05 = 0.41
97.18 = 0.21
Contact
L-STEP
98.16 + 0.09
98.72 0.06
97.25 0.07
97.99 = 0.07
Based on the above analysis, our design gets verified in-depth: the proposed learnable positional encoding is effective and friendly to lightweight neural architectures, and even simple MLPs can fully exploit its expressive power.
H.3. Empirical runtime comparison with SOTAS
Table 1.. Comparison in runtime (in seconds) and number of training epnchs of I-STEP and DyGFormer across 5 runs on US Legis and
UN Trade.
Dataset
Method
Total time for 5 runs (in seconds)
Number of training epochs
L-STEP [287.19, 257.18, 251.49, 248.92, 305.09]
[21, 18, 17, 17, 21]
US Legis
DyGFormer
[1251.97, 1697.56, 1112.50, 756.80, 1092.77]
[27, 37, 24, 16, 23]
FreeDyG
[1019.91, 871.21, 1061.15, 1070.41, 868.031
[17, 13, 18, 18, 13] 21,,21, 18, 18, 19] [33, 55, 53, 25, 95]
L-STEP
[2922.14 2257.11, 2450.84, 2593.40, 2740.26]
UN Trade
DyGFormer
[12847.83, 21167.01, 20380.42, 39374..55
FreeDyG
We present the runtime comparison between L-STEP and DyGFormer (Yu et al., 2023), FreeDyG (Tian et al., 2024), recent SOTA methods, on US Legis and UN Trade datasets, in Table 11. As shown in Table 11, our running time is lower than SOTAs in terms of convergence time.
22

---

Learnable Spatial-Temporal Positional Encoding for Link Prediction
H.4. Empirical results for ablation study
Next, we conduct an ablation study to examine the ability of the learnalle positional encoding in the link prediction task.
Specifically, consider the following cases: (1) only leveraging LPE to make predictions (i.e., omit node/edge features and only employ positional encoding learned by LPE to obtain link predictions); (2) omitting LPE module (i.e., only relying on node and link features).
First, we provide the performance comparison between L-STEP and only using LPE module (denoted as "Only LPE") to obtain link predictions under transductive and inductive settings with random negative sampling strategy. As shown in Table 12, on most datasets, the performance obtained by only leveraging LPE already competitive, which suggests the positional encoding is informative enough support downstream tasks. Also, can observe that LPE positional encodings can collaborate well with node and edge features to boost performance.
Table 12. Comparison between only LPE and L-STEP with random negative sampling strategy.
Transductive setting
Inductive setting
Dataset
AP
ROC-AUC
AP
ROC-AUC
I-STEP
Only LPE
L-STEP
Only L.E
I-STEP
Only LPE
I-STEP
Only LPE
Wikipedia
99.34 0.04 99.07 + 0.03
99.48 + 0.03 99.42 + 0.03
99.15
0.04 98.77 + 0.05
99.30
0.03 98.99- 0.03
Reddit
99.37 + 0.04 98.67 =
=9.4==0000 99.13 = 0.05
98.02 = 0.09 95.44 = 0.29
98.49 0.06 96.71
MOOC
86.94 0.34 81.55 0.53
89.28 0.288 83.04 1 0.44
88.49
0.24 80.04 0.40
90.63 = 0.21 81.701 0.39
Lastfm
96.06 + 0.30 92.84:00
97.52 = 0.17 94.43 + 0.38
96.25 0.43 94.27 =: 0.36
97.66 0.21 96.22 0.22
Enron
93.96 + 0.36 93.82 + 0.44
95.98 + 0.23 95.95 + 0.31 89.17 = 0.88 89.15 +1.32 92.30 + 0.57 92.33 +0.79
Social Evo.
92.22 + 0.25 01.56
94.33 = 0.21 93.76 0.63
91.71 = 0.32 90.421 1.68
94.09 = 0.24 93.28= 0.97
UCI
96.67 + 0.47 96.83
+ 0.19 97.62 + 0.23 97.89 + 0.10 94.60 = 0.41 94.60
+ 0.46
95.88 = 0.17 96.17 +0.22
Flights
98.94 1:44:00 0.10 99.10
= 99.38 = 0.04 99.43
0.06 97.43 = 0.15 97.81
=0.25
98.46 0.07 98.62 #0.11
Can. Parl.
08.24 98.41
0.06 98.97 = 0.06 99.03
0.03
92.25+ 0.24
92.13
0.24
95.06
0.11 95.09 #0.07
US Legis.
76.74 + 0.60 77.36
- 0.26
83.89 12.89:100 0.43 84.36
: 0.20
61.98
= 1.31 63.47
10.63
66.18 = 1.19 66.75 0.57
UN Trade
75.84 2.08 78.46
0.97
83.17 1.28 77.81
1.78 76.80
2.01
84.85+
0.89
83.95
1.76 84.89+ 1.39
UN Vote
73.40 + 0.03 70.99
0.11
79.59 = 0.02
76.67
= 0.09
75.09
0.34
70.01 0.69
82.01
0.21 77.36 #0.51
Contact
98.16 + 0.09 97.73 + 0.04
98.72 + 0.06 98.40 + 0.03 97.25 = 0.07
96.38 0.09
97.99 - 0.07 97.37 0.07
Second, we present the comparison between L-STEP and only using node/edge features, i.e., omitting the LPE module from L-STEP (denoted as "W/o LPE"). As shown in Table 13, L-STEP performs the best on all datasets, further suggesting that performance would be negatively affected without employing LPE.
Table Comparison between not using LPE and L-STEP with random negative sampling strategy.
Transductive setting
Inductive setting
Datasct
AP
ROC-AU AUC
AP
ROC-AUC
L-STEP
W/o LPE
L-STEP
W/ LPE
L-STEP
W/o LPE
L-STEP
Wo LPE
Wikipedia
99.34 + 0.04 96.52 = 0.06 99.48 1 0.03 96.15 1 0.08
99.15 1 0.04
96.11 = 0.09
99.30 1 0.03 95.64
Reddit
99.37 0.04 97.07 + 0.08 99.49
0.03 96.96 + 0.07
98.02
0.09
90.10 0.06
98.49 + 0.06 95.02 9
MOOC
86.94
0.34 81.89 = 0.32 89.28 0.28 $3.24
88.49 =: 0.24 80.65 0.28
90.63 = 0.21 82.19 0.26
LastFM
96.06 + 0.30 74.63 + 0.41 97.52 + 0.17 73.48:1..3
96.25 1 0.43 82.08 + 0.46
97.66 + 0.21 80.74 0.37
Enron
93.96 0.36 82.49 = 0.85 95.98 = 0.23 84.18
89.17 = 0.88 76. 14 = 0.82
92.30 0.57 76.63 0.65
Social Evo.
92.22 1 0.25 91.17 : 0.21 94.33 0.21 93.30
91.71 1 0.32 89.38 1 0.30
94.09 1 0.24 91.85 1 0.24
UCI
96.67 + 0.47 91.79 + 4.08 97.62 + 0.23 00.51+3.44
94.60
0.41 89.58 + 3.41
95.88 + 0.17 87.88 +.18
Flights
98.94 0.10 90.91 = 0.02 99.3 1: 0.04 91.03
97.43=
82.72 = 0.05
98.46 0.07 82.05 0.04
Can. Parl.
98.24 0.11 67.19 + 1.39 98.97
+ 0.06 76.51
92.25 0.24 52.47 + 0.88
95.06 + 0.11 50.99 1.72
US Legis.
76.74 0.60 60.98 + 5.43 83.89
0.43 65.76
61.98
1.31 52.59 + 2.13
66.18
1.19 53.75 1.07
UN Trade
75.84 = 2.08 62.04 = 0.72 83.17
1.28 6..61
76.80 = 61.84
0.53
83.95 - 1.76 63.54 0.54
UN Vote
73.40 0.03 52.29 1 0.44 79.59
0.02
52.55 0.61
75.09 1 0.34
50.74
1 0.82
82.01 1: 0.21 49.39 0.75
Contact
98.16 0.09 91.39 + 0.05 98.72 0.06 93.57 + 0.04
97.25 0.07 89.71 0.05
97.99 + 0.07 92.24 0.05
Combining the results from Tables 12 and 13, we discern that (1) in most cases, the full design of L-STEP is the best and removing any component can lead to suboptimal results, (2) in a few cases, only using LPE can also perform competitively,
23

---

Learnable Spatial-Temporal Positional Encoding for Link Prediction
which suggests that the Learnable Positional Encoding module in our L-STEP is relatively dominating than input node and edge features.
H.S. Empirical results for parameter analysis
H. PARAMETER ANALYSIS FOR Egop
Here, we examine how varying the values of Egap affects the performance of L-STEP under both transductive and inductive settings with random negative sampling.
Table 14, AP and ROC-AUC with various values of tgap under transductive setting and random negative sampling.
Dataset
Metric
1gap = 10
1gop = 50
1gap = 1000
Lopp = 2000
AP
93.77 + 0.28
93.82
0.11
93.96
0.36
93.70 + 0.43
Enron
ROC-AUC
95.83 = 0.14
95.86 : 0.07
95.98
0.23
95.83 = 0.21
AP
73.40 0.03
73.38
73.39
0.08
73.28 = 0.33
UN Vote
ROC-AUC
79.59 = 0.02
79.54
79.57 + 0.06
79.53 = 0.22
Table 15. AP and ROC-AUC with various values of (gop under inductive setting and random negative sampling.
Dataset
Metric
Egap 10
Egap 50
Egap 1000
'gap
2000
AP
88.43 + 0.52
88.76 + 0.62
89.17 = 0.88
88.41 + 0.21
Enron
ROC-AUC
91.83 + 0.37
92.02 + 0.37
92.30 + 0.57
91.86 + 0.24
AP
75.09 + 0.34
75.01 = 0.29
74.92 = 0.48
74.73 + 0.44
Un Vote
ROC-AUC
82.01 + 0.21
79.54 = 0.08
81.85 = 0.32
81.77 + 0.16
We conduct the parameter analysis on two datasets: Enron and UN Vote, and adjusting tgap to different values: {10,50 50, 1000, 2000}. Due to the page limit, we report the results in Table 14 for transductive and Table 15 for in- ductive setting, respectively. The best results are emphasized with bold. Firstly, it worth noting that the ratio #Links (Unique Steps) of UN Vote much larger than that of Enron, since UN Vote has significantly more links and fewer number of unique steps than Enron, as stated in Table 4, implying UN Vote is much denser that Enron. From Tables 14 and 15, we can see that the best performance on UN Vote is derived from goop = 10, which is the smallest value, while the best result on Enron is obtained by much larger value of tgap, which is 1000. These findings indicate that a small tapp value functions effectively for dense graphs, whereas a larger (gap value is suited for sparse graphs. The detailed configurations are reported in Table 22 further suggest this finding, as the Egop values associated with the sparse dataset (Wikipedia, Reddit, MOOC, LastFM, Enron, Social Evo., UCT) mostly are in the range of [1000, 2000), while the fgap values employed for Can. Parl., US Legis., UN Trade, UN Vote, and Contact only less than or equal 10.
We report the results for the parameter analysis regarding how the performance change with different values of t goo Tables 14 and 15.
H.5.2. PARAMETER ANALYSIS FOR K
Next, we conduct parameter analysis for the neighborhood size, K, with random negative sampling, and report the results under transductive and inductive settings in Table 16 and Table 17, respectively.
Table 16. AP and ROC-AUC with various values of K under transductive setting and random negative sampling.
Dataset
Metric
K = 5
K 20
K 50
K = 100
AP
93.32 + 0.25
93.96 + 0.36
93.53 + 0.51
93.22 + 0.38
Enron
ROC-AUC
95.50 = 0.16
95.98 + 0.23
95.71 + 0.31
95.48 + 0.19
AP
72.08 = 0.73
73.40 = 0.03
73.49 + 0.10
73.31 - 0.13
UN Vote
ROC-AUC
78.92 + 0.33
79.59
0.02
79.69 0.10
79.58 + 0.08
According to the tables, we can discern that: (1) in a few cases, increasing K can slightly increase the performance, but it is prone to cost more computational complexity; (2) in most cases, increasing K does not add much to the performance, which
24

---

Learnable Spatial-Temporal Positional Encoding for Link Prediction
Table 17. AP ROC-AUC with various values of under inductive setting and random negative sampling.
Dataset
Metric
K =
K = 20
K = 50
K = 100
AP
89.72 + 0.50
94.60 + 0.41
88.99 + 1.04
88.29 + 0.58
Enron
ROC-AUC
92.65 + 0.33
95.88 + 0.17
92.11 + 0.65
91.64 + 0.36
AP
77.76 = 0.49
75.09 = 0.34
75.10 + 0.34
73.92 = 0.75
UN Vote
ROC-AUC
83.73 + 0.23
83.95
1.76
81.96 0.25
80.94 + 0.82
suggests that close neighbors have already had enough information to support downstream tasks.
H.5.3. PARAMETER ANALYSIS FOR L
Here, we report the parameter analysis for L as follows on Can. Parl. dataset in Table 18.
Table 18. AP and ROC-AUC with various values of L under transductive setting and inductive sefting with random negative sampling.
Dataset
Transductive AP
Transductive ROC-AUC
Inductive AP
Inductive ROC-AUC
L = 20
98.24 + 0.11
98.97 + 0.06
92.25 + 0.24
95.06 + 0.11
L 50
98.26 + 0.06
98.94 + 0.03
92.15 = 0.34
95.11 + 0.17
Can. Parl
L 100
98.11 + 0.21
98.85 + 0.11
92.16 + 0.98
95.25 + 0.56
L 200
97.04 0.22
98.37 + 0.09
91.96 0.59
95.19 + 0.38
From Table 18, we can observe that our proposed L-STEP just relies on looking back a few historical information make the correct information, L increases, the performance be downgraded, and the best performance exists between 20 and 50, which discovery demonstrates that the near past history plays important role in the current decision making than the long past history.
H.5.4. PARAMETER ANALYSIS FOR Onne
We present the parameter analysis for Oneg on Can. Parl. dataset Table 19.
Table 19. AP and ROC-AUC with various values of Oneg under transductive setting and inductive setting with random negative sampling.
Dataset
Transductive AP
Transductive ROC-AUC
Inductive AP
Inductive ROC-AUC
Aneg = 0.05
98.26 + 0.13
98.98 + 0.05
92.24 + 0.09
95.09 + 0.11
Oneg 0.1
98.28 + 0.09
98.98 + 0.05
92.35 = 0.21
95.09 + 0.09
Can. Parl
Oneg 0.3
98.24 0.11
98.97 0.06
92.25 = 0.24
95.06 + 0.11
Oneg 0.5
98.28 + 0.13
98.97 + 0.05
91.48 + 0.23
94.75 + 0.16
Oneg 0.95
98.24 + 0.18
98.95 + 0.09
91.09 + 0.49
94.53 + 0.32
In general, Table shows (1) our proposed method L-STEP is robust towards different choices of aneg. and (2) usually a smaller weight of negative pairs help the model concentrate the positive pairs and boost the performance.
H.5.5. PARAMETER ANALYSIS FOR O'ee
We present the parameter analysis for Onneg on Enron dataset in Table 20.
Onag stands for the weight of the loss function of learnable positional encoding. As shown in the Table 20, we can observe that (1) our L-STEP robust towards different choices of Ope. and (2) a considerable weight, e.g., 0.5, is optimal, too large or too small weight can induce suboptimal results.
25

---

Learnable Spatial-Temporal Positional Encoding for Link Prediction
Table 20. and ROC-AUC with various values ape under transductive setting and inductive setting with random negative sampling.
Dataset
Transductive AP
Transductive ROC-AUC
Inductive AP
Inductive ROC-AUC
O pe 0.05
92.81 + 0.82
95.32 = 0.38
86.49 + 1.52
90.91 0.61
pe = 0.3
93.96 + 0.36
95.98 = 0.23
89.17 + 0.88
92.30 = 0.57
Enron
Pe 0.5
93.94 = 0.10
95.90 = 0.06
88.92 = 0.39
92.12 = 0.22
pe = 0.95
94.00 + 0.28
95.92 = 0.17
88.67 + 0.34
91.91 = 0.30
H.6. Different positional encoding initialization
In this section, we demonstrate that L-STEP can be equipped with different positional encoding method, other than Laplacian PE. Specifically, our work aims to introduce general framework on how to approximate positional encodings at a current time solely based on information from previous timestamps to outperform in temporal link prediction task, and we do not want constraint the type of positional encodings. In Table 21, we provide the comparison between initializing the positional encodings initial timestamp with Laplacian PE and Random Walk PE (Dwivedi et al., 2022) under two settings, transductive and inductive, with random negative sampling.
Table 21. Comparison Positional Encoding initialization with Laplacian and Random Walk Positional Encoding under transductive and inductive settings with random negative sampling.
Dataset
Positional Encoding
Transductive AP
Transductive ROC-AUC
Inductive AP
Inductive ROC-AUC
Random Walk PE
93.79 + 0.67
95.88 + 0.40
89.11 + 0.83
92.43 + 0.64
Enron
Laplacian PE
93.96 + 0.36
95.98 + 0.23
89.17 + 0.88
92.30 + 0.57
Based on Table 21, we can discern that (1) L-STEP can handle different positional encodings and perform robustly; (2) different positional encodings bring slightly different performances and finding a powerful positional encoding is a promising future direction trigger more interesting works.
I. Reproducibility
I.1. Different Negative Sampling Strategies (NSS)
In brief, random NSS samples possible node pairs uniformly at random, historical NSS samples negative edges from the edges occurring in past timestamps but are absent in the present time, and inductive NSS samples edges that are unseen during the training time. We refer readers to (Poursafaei et al., 2022) for more details regarding these three sampling strategies.
Configuration and implementation details. Following the training procedure of (Yu al., 2023), L-STEP trained with maximum of 200 epochs, and employ early stopping with patience 10 during the training process. We leverage the Adam optimizer with learning rate of 0.0001. For more detailed description of the model's implementation, computational resources, and configurations of hyper- parameters over all 13 datasets, we refer readers to Appendix 1.2, I.3.
Across Table 1, Table 5, Table 6, Table 7, Table 8, and Table 9, the model with the best performance, in terms of metric scores AP and AUC-ROC, on the validation set will be selected for testing. We run L-STEP 5 times with different random seeds from 0 to and report the average metric score. Results from all other baselines are also obtained in the same manner (Yu et al., 2023).
1.2. Model Configurations, Hyper-parameters, and Computing Resources
We first report the configuration and hyper-parameters that are unchanged for all datasets:
Dimension of time encoding: dr 100.
Dimension of node encoding: dx 172.
Dimension of edge encoding: dg 172.
26

---

Learnable Opatial-Tempordl Positional Encoding for Link Prediction
Dimension of positional encoding: dp 172 (only for Social Evo., dp 72).
Hyper- parameters for time encoding function: a 10, 3 = 10.
Weight of negative samples in positional encoding loss: Onneg = 0.3.
Weight of positional encoding loss in objective loss function of L-STEP Ope 0.5.
Table 22. Configurations of the number of recent snapshots for computing LPE, time window for node features, recent interactions for
edge features, and batch size over 13 datasets
Dataset
L
Egap
K
Batch size
Wikipedia
100
1000
15
128
Reddit
100
1000
20
200
MOOC
100
2000
30
128
Lastfm
100
1000
30
128
Enron
100
1000
20
64
Social Evo.
100
1000
20
128
UCI
200
500
30
100
Flights
100
1000
30
128
Can. Parl.
20
2
10
64
US Legis.
50
2
10
200
UN Trade
200
6
30
200
UN Vote
100
10
20
128
Contact
200
10
20
128
The experiments coded by Python and are performed Linux machine with single NVIDIA Tesla V100 32GB GPU, The code will be released upon paper's publication.
Next, for reproducibility, we present detailed
across 13 datasets in Table 22.
I.3. Running L-STEP on Continuous Time Dynamic Graphs
The definition of discrete time and continuous time dynamic graphs can be referred to the survey paper (Kazemi et al., 2020),
where
Continuous Time Dynamic Graph (CTDG) is represented as ((v2,u),,11. (1),))) ((v1, ((v1, (2), 12)..... .... as shown in its Example
2;
Discrete Time Dynamic Graph (DTDG) is represented set of G1, G2,...,, Gr, where G. (V,, Fi.) is the graph snapshot t, V2 is the set of nodes in GG. and E, is the set of edges in Gt.
In this viewpoint, method is designed for discrete time. However, we DTDG: if we aggregate edges that happen at the same timestamp into set, then it is the graph snapshot Gg. This is not invented by us, similar example can be seen in Example 3 of the survey paper (Kazemi et al., 2020).
clear transformation between CTDG and
Because the introduction and theoretical derivation on the snapshot level are much easier to understand by people, and using "a set of continuous-timg edges" every time when we do theoretical derivation and illustration can be wordy and hurt the presentation. Since graph snapshot and relevant concepts are already existing in the community and cover the meaning, then we choose to follow them.
Then, in this section, elaborate how L-STEP can be evaluated on Continuous Time Dynamic Graphs. Firstly, explain the data batching procedure for Continuous Time Dynamic Graphs follows. Suppose we are given a CTDG with T interactions, G = [4, v;, t 4 where t < 'o and (u,, Vs, t.) denotes the link occurrence between U; Uy at time t, Let the batch size be B, then a data batch would be B consecutive interactions from {u, 21, t TT Specifically, suppose T= B- K (for some K), then our 1st data batch would be the first B link occurencees of G: (u,, U, t The 2nd data batch would be the next B consecutive interactions, {wi, U/ &, 12B B+1 and so on. In this way, now we obtain K data
27

---

Learnable Spatial-Tempone Positional Encoding for Link Prediction
batches. Moreover, batch is stream of B events, occurrences. This data batching technique is also employed by other baselines.
regard data batch as mini temporal graph with B link
Next, we explain the evaluation process of L-STEP. Consider an arbitrary data batch (3. data batch, then first extract all links occurrence (without the timestamps), {uj, My ) transform this to static graph, and obtain the Laplacian eigenvectors of this graph to initialize the positional encoding for each node. If a node of G does not belong to this graph then we initialize the positional encoding of that node with zero vector. Here, let the "initial" positional encoding for node u as p... As we advance to the 2nd data batch, we first compute the approximated positional encoding for all nodes, p", as stated Eq. 1, 2, based on p this way, following Eq. 1, 2, we can iteratively compute the approximate positional encoding for the k-th batch, p.,, based on the sequence of previous L positional encodings, p. p ,...,,."
V/, Uy. Ty If this is the first
corresponding to previous I. data batches.
For our current data batch (suppose this the k-th batch), {uj, Uy Ti) we now describe how obtain the link predictions. For each query (u,, Vy Ty], we obtain b", Will as defined in Eq. 6, and h p. as stated in Eq. 8, using Puy- Finally, we combine MiI h .. obtain the temporal representation time Tj for uj. h.z. Similarly, we obtain the temporal representation for Vj. hng Finally, following Eq. 10, obtain the link prediction for (uj, By, TT) using h hay.
In summary, we ideally would want to obtain the positional encoding of node u, Pu E TRd for every temporal graph snapshot. However, for training efficiency, our implementation computes the positional encoding for the graph corresponding to data batch.
28


Reviews:
[{"review_id": "tpwPWpYRrI", "reviewer": "Reviewer_U1pJ", "summary": "The paper introduces a new method for predicting connections in networks that change over time. Instead of using fixed rules or complex models that require a lot of computing power, L-STEP learns how positions in the network change over time using the Fourier Transform. The authors show that their approach keeps important information about the network’s structure and performs as well as more complicated models. They test it on 13 datasets and two large benchmark datasets and find that it predicts connections better than existing methods.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for your review! We are excited to learn your appreciation of our extensive experiments and corresponding outperformance. \n\nYour suggestions are quite actionable, and we seriously prepared the answer in Q&A format below.\n> W1: The low changing aspect needs to be tested. \n\nFirst, the outperformance of our method across all 15 real-world datasets has proven our theoretical design is valid to some extent.\n\nOf course, we understand your concern, and prepared the illustration of the slowly changing pattern in the real-world graphs below, by taking UNVote dataset as an instance. The assumption is further proved, and we promise to add this new content to our camera-ready version. \n\n[**Positional Encoding Patterns with Time**]\n- In the 1st plot of [UNvote](https://docs.google.com/document/d/e/2PACX-1vTPt6EJ-gnmGwZgW9Lth0UgAukqk4pPqSFPFQhJBIy6QRMe4e6Az6kIo5eGRQ1dYOBl_PGI0IHBJkBL/pub), the x-axis represents timestamps, and y-axis represents the distance between each consecutive pair of positional encoding, i.e, $\\mathbf{p}^t$ and $\\mathbf{p}^{t + 1}, \\forall t$. As $\\mathbf{p} \\in \\mathbb{R}^{|V| \\times d_P}$, which is a matrix and $i$-th row is the positional encoding of node $i$\n  - We compute the distance between $\\mathbf{p}^t, \\mathbf{p}^{t + 1}$ by first computing the Euclidean distance between $\\mathbf{p}\\_u^t$ and $\\mathbf{p}^{t + 1}\\_u$ and then let the mean of Euclidean distance of positional encoding overall all nodes, i.e, $\\frac{1}{|V|} \\sum_{u \\in V} d(\\mathbf{p}\\_u^{t}, \\mathbf{p}\\_u^{t + 1})$, be the distance between $\\mathbf{p}^t$ and $\\mathbf{p}^{t + 1}$. \n  - We discover the distance between each consecutive pair of positional encoding, $\\mathbf{p}^{t}$ and $\\mathbf{p}^{t + 1}$ is consistently small across all timestamps. \n- In the 2nd plot, we illustrate the distance between our learned positional encoding and the true positional encoding for each graph snapshot\n  - Overall, the distance between our learned positional encoding and the true positional encoding of each snapshot is consistently small across all timestamps.\n\n[**Theoritical Explaination**]\n\nTo further address your concern, we would like to go through Theorem 1 intuitively for you. In short, it shows that when the temporal graph is slowly evolving with respect to time, the learned positional encoding at previous timestamp can well approximate the next close future timestamp’s positional encodings.\n\nTheoretically, the significance of Theorem 1 is to demonstrate the effectiveness of our proposed LPEs in the inductive setting, where future graph structural information is hard to observe, such that the “slowly changing” assumption for the coming snapshots is needed for this theoretical derivation. Moreover, defining a degree of change over temporal snapshots is an interesting but largely open question, which may involve the random matrix theory and relevant knowledge [1], and so far no clear definition, to the best of our knowledge.\n\nTherefore, **assuming the temporal smoothness [1], i.e., next snapshot will not change dramatically from the previous snapshot** is a quick-win solution for the theoretical derivation, and we are more than happy to dive in this topic for our future research direction.\n\n[1] Chi et al., Evolutionary Spectral Clustering by Incorporating Temporal Smoothness, KDD 2007\n> W2: Available code. \n\nWe promise to publish our code upon the paper’s publication. Also, we are preparing an anonymous link, so we can share the implementation shortly (before the deadline for final response). \n> W3: Hyperparameter sensitivity.\n\nBased on our parameter analysis, our model is comparatively robust to bad choices, i.e., we experience drops in performance while varying the hyperparameter but the drops are not significant. For more details and intuition for choosing the hyperparameter, please refer to Appendix H.5.\n> Q1: Why are FreeDyG results missing in table 11?\n\nOriginal FreeDyG did not run on UNTrade dataset. We follow FreeDyG’s official implementation, but the corresponding performance is around 0.500. We will add this explanation to our camera-ready version.\n> Comment 1: The main article does not contain dataset descriptions and most of the reported results. \n\nDue to page limit, the description is in Appendix G. Results of other experimental settings (historical and inductive negative sampling), ablation study, and parameter analysis are in Appendix H.\n> Comment 2: L-step results are bolded in table 2 right panel but these are not the best results.\n\nTable 2 is ranked from top to bottom with a ranking index; we bold our method for just highlighting its position.\n> Suggestion: I would like to see an HTGN comparison to see how it compares to hyperbolic methods, but there are two recent and A+ articles. They seem enough.\n\nWe understand, and we are adapting HTGN to this paper's setting. If finished early, we will post HTGN’s results before the final response deadline. If not, we will add it to our camera-ready version.", "claims_and_evidence": "- Yes, the results are supported by experiments on datasets.", "methods_and_evaluation_criteria": "yes, the methods and criteria are appropriate", "theoretical_claims": "I checked the theorem in the appendix.", "experimental_designs_or_analyses": "I checked theorem 4.1, and it depends on the graph's slow change. For this claim to be dependable, the authors must have shown that slow change is a phenomenon in real graphs.", "relation_to_broader_scientific_literature": "- The article studies the long and well-studied problem of predicting edges that have already appeared in the past. In this sense, I do not see much novelty. However, they also propose a learnable positional encoder, and this is novel.", "essential_references_not_discussed": "- I would like to see an HTGN comparison (not our article) to see how it compares to hyperbolic methods, but there are two recent and A+ articles. They seem enough.\n\nYang, M., Zhou, M., Xiong, H. and King, I., 2022. Hyperbolic temporal network embedding. IEEE Transactions on Knowledge and Data Engineering, 35(11), pp.11489-11502.", "other_strengths_and_weaknesses": "Strengths:\n\n- The article is quite detailed and have covered almost all potential analyses in the appendix. The baselines are strong and the studied datasets are many. I appreciate the sensitivity analysis in the appendix. \n\nWeaknesses:\n\n - The article has quite many components that require everything to go as expected.  The low changing aspect needs to be tested. Many models break down in sparse graphs or highly dynamic environments, but the authors do not analyze cases where the graph changes too quickly for their positional encoding estimation to remain accurate.\n-  The code is not shared. I would raise a bigger issue about this, but the detailed results in the appendix are the saving grace, and I will assume that the authors will share the code soon.\n- The hyperparameter analysis suggests that L-STEP performs well within a certain range, but does not discuss how sensitive the model is to bad choices.", "other_comments_or_suggestions": "- The main article does not contain dataset descriptions and most of the reported results.  \n- Lstep results are bolded in table 2 right panel but these are not the best results. It is misleading to bold them.", "questions_for_authors": "- Why are FreeDyG results missing in table 11?\n- An interesting assumption is that you try to learn a function to estimate a positional encoding of u at time t. However, predicting an exact positional encoding assumes a high degree of regularity in graph evolution, which may not hold in real-world networks. That part is not quantified by using synthetic graphs. You also do not try to quantify it in datasets and compare your performance as a function of that change.", "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": "", "extra_scores": {}}, {"review_id": "4sAKFJWJ2l", "reviewer": "Reviewer_ia3A", "summary": "This work explores the problem of temporal link prediction, and proposes a semi-non-graph model that shows quite good performance across a variety of datasets. Their model, LSTEP, works by introducing a learnable time-dependent positional encoding, where the time dependence is parameterized by a learnable fourier kernel. This idea is simple but seems to provide reasonable performance.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your appreciation of our method’s soundness and experimental design! Addressing your concerns improved the quality of our paper, and we prepared the answer below.\n\n> How learnable positional encodings work in dynamic environment.\n\nDue to the length limit of response, we sincerely invite you to check our first answer in U1pJ\n\n> W1: First paragraph of section 3.1 is a large run-on sentence, use LLM to refine.\n\nThanks, we will.\n\n> Q1: What is the spectrum of filtered noise in your experience? \n\nWe would like to elaborate on what kind of information our learnable filter (used in Eq (1)) learns.\n\nTheoretically, we first apply DFT on $u$’s sequence of learned positional encodings at previous timestamps {$\\mathbf{p}^{t’}_u$}, then the learnable filter filters out high-frequency noise across dimensions of the learned positional encodings in the spectral domain, and finally, the Inverse DFT transformed the filtered positional encodings back to the original domain. \n\nPractically, the filtered noises are those that cannot contribute to link prediction decisions.\n\n> Q2: By using the DFT to model ...\n\nFirst, to our understanding, the sequence is not necessarily wave-like to be decomposed by DFT, so we do not constrain our positional encoding to follow any wave-like dynamics. In addition, we did not consider applying cosine or sine bases, since DFT’s bases already contain cosine and sine components. \n\n> Q3: How is p0 computed for a new vertex?\n\nIf a new vertex emerges, we first initialize this vertex’s positional encoding to a zero-valued vector, then proceed with the model's computations to make link predictions involving this vertex. \n\n> Q4: How does the DFT relate to ...\n\nWe clarify the difference between DFT and traditional graph fourier transform, then elaborate on why employing DFT is more suitable for the temporal link prediction problem as follows. \n\nDFT is leveraged for processing time-series-like data, while graph fourier transform analyzes the signal associated with nodes of a graph. Intuitively, the signals in time-series are defined along a timeline, i.e., each timestamp on the timeline produces a signal, while graph fourier transform processes signals defined on nodes of a graph, i.e., each node is associated with a signal, for example, each node of the graph has a node feature vector.\n\n- In our framework, we are trying to “approximate” a node $u$’s positional encoding at time $t$ based on its positional encodings in previous $L$ most recent distinct timestamps, $\\{\\mathbf{p}\\_u^{t’\\_j}\\}\\_{j = 1}^L (t’\\_j < t, \\forall j)$, so through the lens of DFT, we can consider $\\{\\mathbf{p}\\_u^{t’\\_j}\\}\\_{j = 1}^L$ as a sequence of signals defined on a timeline, where each timestamp $t’\\_j$ produces the signal $\\mathbf{p}\\_{u}^{t’\\_j}$.\n- Graph fourier transform (GFT) acts as a convolution on the graph, i.e., GFT computes a node’s representation based on other nodes’ information and GFT is defined for static graphs, while we only want to obtain a node’s positional information based on its positional information at previous timestamps, so we think that DFT is a better fit for our goal.\n- Due to the difference in the definition and setting between DFT (for sequences, temporal data) and GFT (for static graphs), we do not expect the filter of L-STEP to be similar to the filters learned by traditional MPNNs. \n\nIn short, we aim to analyze the temporal dependencies in the sequence of node $u$’s positional encodings at different timestamps, so we employ DFT, which is a better fit for sequences and time-series-like data, while GFT operates convolution on static graphs.\n\n> Q5: How did you implement the complex-valued gradient ...\n\nIn our implementation, we first initialize $\\mathbf{W}\\_{filter}$ using nn.Linear() module of PyTorch library and then convert the parameter to torch.complex64 data type, i.e., turning $\\mathbf{W}\\_{filter}$ into a complex-valued tensor. Now, we present our implementation to obtain Eq (1) as follows. Suppose ```batch_pe``` is $\\{\\mathbf{p}\\_{u}^{t’\\_j}\\}\\_{j = 1}^L$ and ```filter``` is $\\mathbf{W}\\_{filter}$.\n\nThe pseudocode for implementing Eq (1) could be described as follows:\n```python3\n1. filter = nn.Linear(d_P, L, bias = False).to(torch.complex64) // initialization of W_{filter}\n\nFor epoch in range(num_epochs): // model training phase\n   2. batch_pe = batch_pe.to(torch.complex64) // convert batch_pe to complex-valued tensor        \n   3. batch_pe = fft.fftn(batch_pe, dim = 1) // apply FFT transformation on batch_pe\n   4. batch_pe = filter.weight.unsqueeze(0) * batch_pe \n   5. batch_pe = fft.ifftn(batch_pe, dim = 1) // apply inverse FFT\n   6. batch_pe = batch_pe.to(torch.float32) // convert back to float32 data type\n```\n\nHere, the 4th line of the pseudo code represents $\\mathbf{W}\\_{filter} \\odot \\mathcal(\\{\\mathbf{p}\\_{u}^{t’\\_j}\\}\\_{j = 1}^L)$, and the 5th line is equivalent to applying inverse DFT. Finally, we convert ```batch_pe``` back to real-valued tensors.", "claims_and_evidence": "The claims are reasonably supported, with good performance across many datasets. I appreciate the ablation experiments that compare LPE with the full model as well as the exploration of parameter sensitivity.\n\nIt's interesting that LSTEP performs comparatively worse on both TGBL datasets, and that in most settings the lifts aren't statistically significant. Would you care to comment?", "methods_and_evaluation_criteria": "Yes, the experiments absolutely make sense and the benchmark datasets can be viewed is as close to exhaustive as is likely possible.", "theoretical_claims": "The theoretical claims in section 4 seem ancillary to the point of the paper, and doesn't seem to meaningfully explain why these positional encodings work. Furthermore, the theoretical analysis makes an adiabaticity assumption, which is probably sufficient for the setting where you have a relatively mature graph at time t1, and then it evolves without changing the community structure too much. I wonder how this theorem holds during the initial growth phase of a preferential attachment style generative process. It would see that the adiabaticity of the graph isn't there, and thus the model wouldn't really hold, but I'd love the authors thoughts on the matter.", "experimental_designs_or_analyses": "I reviewed the experiments presented in section 5 as well as the appendices. As presented, nothing seemed unexpected but I did not reimplement the model.", "relation_to_broader_scientific_literature": "As mentioned above, the ideas in this paper aren't particularly novel. For example, the use of a DFT to compute evolving PEs isn't new. While the theoretical and methodological contributions seem to be limited, they are combined in a way that leads to a simple to understand model with relatively significant performance gains. Because ML is an empirical science, I believe it's important to make space for papers which don't maximize novelty if they refine these ideas in a way that leads to significant empirical gains.", "essential_references_not_discussed": "Not to my knowledge", "other_strengths_and_weaknesses": "**Other Weaknesses**\n- The paper is poorly written, which can make it hard to follow in spots. For example, the first paragraph of section 3.1 is a large run-on sentence. I would recommend that the authors give the paper a thorough grammatical review. Language modeling tools like chatgpt or claude can be quite effective for this.", "other_comments_or_suggestions": "See other strengths and weaknesses", "questions_for_authors": "1. What is the spectrum of filtered noise in your experience? Do you\n2. By using the DFT to model temporal propagation, you're essentially assuming wave-like dynamics because the wave equation's time-propagater can be expanded in terms of a the fourier basis. Have you explored other possible bases? For example, cosh/sinh to model diffusion?\n3. How does this model work in an inductive setting? Specifically, how is p0 computed for a new vertex?\n4. How does the DFT presented here relate to the traditional graph fourier transform that's defined by the eigensystem of the laplacian? Is the filter that's learned in LSTEP expected to be in any way similar to the filters learned by traditional MPNNs? If not, could you comment on why this DFT appears to perform better?\n5. How did you implement the complex-valued gradient of W? This can be quite a nuanced topic, so I'm curious as to how it works.", "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": "", "extra_scores": {}}, {"review_id": "9UpN4Xofga", "reviewer": "Reviewer_uGHA", "summary": "This paper introduces a framework L-STEP for learning representations on discrete temporal dynamic graphs, which comprises two key components: 1) LPE (Learnable Positional Encoding): a learnable spatial-temporal positional encoding designed to capture evolving graph topology from a spectral viewpoint. Concretely, LPE approximates positional encodings by applying the Discrete Fourier Transform (DFT) over past positional encodings. 2) A Node-Link-Positional Encoder for computing temporal node representations. Experiments are done to validate the effectiveness of L-STEP.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for your review!\n\nWe are excited to learn your appreciation of our model's design, effectiveness and efficiency, and paper's writing.\n\nYour suggestions are actionable and helpful.\n\nFirst of all, we correct the typo in Eq (11) and promise to update it in our camera-ready version.\n\nThen, we would like to further discuss your concern in the experimental setting.\n\n[**Data Source**]\n\nThe datasets used in our paper, according to [2], is firstly collected by [1].\n\nHowever, as a library, [2] provides detailed all dataset processing and baseline implementation, https://github.com/yule-BUAA/DyGLib, and we used all the datasets from [2].\n\n[**Implemtation**]\n\nWe strictly followed the implementation of [2] and reported the performance. \n\nFor more clarification, we follow the training and evaluation settings of [2] as follows.\n\n- Specifically, during training, we compute the loss function and perform back propagation for the model only using randomly sampled negative links.\n- Then, with this trained model, we test the model on random, historical, and inductive negative edges. \n- The corresponding configurations are listed in Appendix I of the paper.\n\n[**Proof from Other Sources**]\n\nBeyond 13 classic datasets in [2], we also tested our method on the open-source worldwide large-scale benchmark leaderboard, TGB [3] (https://tgb.complexdatalab.com/docs/leader_linkprop/), which also provides the standard dataset split and training paradigm.\n\nIn TGB, our method also achieves a very competitive performance in temporal link prediction tasks, as shown in Table 2 of the paper.\n\n[**Code Release**]\n\nWe promise to release our code upon publication.\n\n---\n\nReference\n\n[1]: Poursafaei, Farimah, et al. \"Towards better evaluation for dynamic link prediction.\" Advances in Neural Information Processing Systems (2022)\n\n[2]: Yu, Le, et al. \"Towards better dynamic graph learning: New architecture and unified library.\" Advances in Neural Information Processing Systems (2023)\n\n[3]: Gastinger, J., Huang, S., Galkin, M., Loghmani, E., Parviz, A., Poursafaei, F., Danovitch, J., Rossi, E., Koutis,\nI., Stuckenschmidt, H., Rabbany, R., and Rabusseau, G. TGB 2.0: A benchmark for learning on temporal knowledge graphs and heterogeneous graphs, Advances in Neural Information Processing Systems (2024)", "claims_and_evidence": "Line 241, the binary cross-entropy loss function in Equation (11) seems incorrect. The second part should be $log(1 - \\hat{y})$, instead of $(1 - log(\\hat{y}))$.", "methods_and_evaluation_criteria": "Please kindly refer to Other Strengths And Weaknesses.", "theoretical_claims": "Please kindly refer to Other Strengths And Weaknesses.", "experimental_designs_or_analyses": "Please kindly refer to Other Strengths And Weaknesses.", "relation_to_broader_scientific_literature": "None.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The design of LPE is clear. The authors provide a rationale for using DFT in positional encoding computation, that is, positional encodings could be regarded as signals on graphs and DFT can be applied to filter noises caused by randomness or entity activities. Experimental results show that LPE significantly improves the performance of downstream tasks.\n    \n2. L-STEP is efficient. The authors show in Section 4 that, in certain scenarios, the proposed encoder is more efficient than methods that rely on neighborhood co-occurrence for node embedding computation. Besides, the L-STEP contains a novel loss function for learning representations on discrete temporal dynamic graphs, as outlined in Equation (13).\n\n3. The paper is well written and easy to follow.\n\nWeaknesses:\n\nL-STEP is thoroughly evaluated on recent and widely used datasets collected by [1], using evaluation metrics that are commonly adopted in prior studies [1, 2]. However, I do have some concerns regarding the use of negative links in the training and evaluation process. Specifically, in Section 3.3, the authors seem to employ three different negative sampling strategies—random, historical, and inductive—during the loss computation. In contrast, the code implementation from [2] trains models using randomly selected negative edges and tests them on random, historical, and inductive negative edges, respectively. \n\nThe experiment settings seem to be different. Since the results for the historical and inductive negative edge settings, where L-STEP significantly outperforms the previous state-of-the-art [2], are directly taken from the result tables in [2], the evaluation and subsequent conclusions could potentially be affected.\n\n[1]: Poursafaei, Farimah, et al. \"Towards better evaluation for dynamic link prediction.\" Advances in Neural Information Processing Systems (2022)\n[2]: Yu, Le, et al. \"Towards better dynamic graph learning: New architecture and unified library.\" Advances in Neural Information Processing Systems (2023)\n\nIf this concern can be addressed with thorough analysis and concrete evidence, my rating can be raised.", "other_comments_or_suggestions": "Please kindly refer to Other Strengths And Weaknesses.", "questions_for_authors": "Please kindly refer to Other Strengths And Weaknesses.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces L-STEP, a novel learnable spatial-temporal positional encoding framework for temporal link prediction. The method leverages Discrete Fourier Transform (DFT) to learn dynamic positional encodings efficiently, avoiding reliance on costly attention mechanisms. The authors demonstrate strong empirical performance across 13 datasets and the TGB benchmark, with theoretical analysis supporting the model’s effectiveness under slow graph evolution assumptions. The authors should: 1) Clarify the slow evolution assumption’s scope. 2) Improve the writing. 3) Add the full TGB datasets comparisons, and properly cite and discuss the leaderboard baselines. 4) Add wall-clock efficiency experiments. Conditioned on the above, I would like to recommend an acceptance.
Decision: Accept (poster)