Improving Temporal Link Prediction via Temporal Walk Matrix Projection
Authors: Xiaodong Lu
Leilei Sun
Tongyu Zhu
Weifeng Lv
Venue: NeurIPS 2024 poster (2024)
Keywords: Temporal Link Prediction
Dynamic Graph Learning
Graph Neural Network
Primary area: graph_neural_networks
TL;DR: This paper unifies existing pairwise information injection methods for temporal link prediction into a function of temporal walk matrices and introduces an efficient method for maintaining temporal walk matrices

Abstract: Temporal link prediction, aiming at predicting future interactions among entities based on historical interactions, is crucial for a series of real-world applications. Although previous methods have demonstrated the importance of relative encodings for effective temporal link prediction, computational efficiency remains a major concern in constructing these encodings. Moreover, existing relative encodings are usually constructed based on structural connectivity, where temporal information is seldom considered. To address the aforementioned issues, we first analyze existing relative encodings and unify them as a function of temporal walk matrices. This unification establishes a connection between relative encodings and temporal walk matrices, providing a more principled way for analyzing and designing relative encodings. Based on this analysis, we propose a new temporal graph neural network called TPNet, which introduces a temporal walk matrix that incorporates the time decay effect to simultaneously consider both temporal and structural information. Moreover, TPNet designs a random feature propagation mechanism with theoretical guarantees to implicitly maintain the temporal walk matrices, which improves the computation and storage efficiency. Experimental results on 13 benchmark datasets verify the effectiveness and efficiency of TPNet, where TPNet outperforms other baselines on most datasets and achieves a maximum speedup of $33.3 \times$ compared to the SOTA baseline.

Improving Temporal Link Prediction via Temporal Walk Matrix Projection
Xiaodong Lu
Leilei Sun
CCSE Lab, Beihang University Beijing, China Alaodonglusbuaa. edu.
CCSE Lab, Beihang University Beijing, China
leileisun@bua. edu. cn
Tongyu Zhu
Weifeng Lv CCSE Lab, Beihang University Beijing, China Iwf@buaa.edi en
CCSE Lab, Beihang University
Beijing, China
zhutongyu@buaa.edn edu.
Abstract
Temporal link prediction, aiming at predicting future interactions among entities based on historical interactions, is crucial for series of real-world applications. Although previous methods have demonstrated the importance of relative encodings for effective temporal link prediction, computational efficiency remains major concern in constructing these encodings. Moreover, existing relative encodings are usually constructed based structural connectivity, where temporal information is seldom considered. To address the aforementioned issues, we first analyze existing relative encodings and unify them function of temporal walk matrices. This unification establishes a connection between relative encodings and temporal walk matrices, providing more principled way for analyzing and designing relative encodings. Based on this analysis, we propose new temporal graph neural network called TPNet, which introduces temporal walk matrix that incorporates the time decay effect to simultaneously consider both temporal and structural information. Moreover, TPNet designs a random feature propagation mechanism with theoretical guarantees to implicitly maintain the temporal walk matrices, which improves the computation and storage efficiency. Experimental results on 13 benchmark datasets verify the effectiveness and efficiency of TPNet, where TPNet outperforms other baselines on most datasets and achieves maximum speedup of 33.3x compared to the SOTA baseline. Our code can be found at /ttps://github com/1xd99/TPNer
Intorduction
Many real-world dynamic systems can be abstracted as temporal graph [1], where entities and interactions among them are denoted as nodes and edges with timestamps respectively. Temporal link prediction, aiming at predicting future interactions based on historical interactions, is fundamental task for temporal graph learning, which can not only help us understand the evolution pattern of the temporal graph but also is crucial for series of real-world tasks such recommendations for online platforms [2, 3] and information diffusion prediction [4, 5].
Relative encodings have become an indispensable module for effective temporal link prediction [6-9] where, without them, node representations computed independently by neighbor aggregation will fail
"oorrsponding Author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

to capture the pairwise information. As the toy example shown in Figure 1, A and F will have the same node representation due sharing the same local structure. Thus it can not be determined whether D will interact with A or F at L3 according to their representations. However, by assigning nodes with relative encodings (i.e., additional node features) specific to the target link before computing the node representation, we can highlight the importance of each node and guide the representation learning process to extract pairwise information. For example, in Figure I, we can infer from the relative encoding of E (in red circle) that D is more likely to interact with F than with A since D and share a common neighbor, E (detailed discussed in Section 2.2). Although achieving remarkable success, injecting pairwise information based on relative encodings is still far from satisfactory. 1) On Concept, existing ways of constructing relative encodings are fragmented as they are de- rived from different heuristics. There still lacks unified view on the connections between differ- ent relative encodings, which may allow a more principled way to design new relative encodings. 2) On Method Design, most existing relative encodings are constructed based on structural connectivity between nodes (e.g., whether two nodes are neighbors), while the temporal infor- mation is ignored. 3) On Computation, ex- isting methods for relative encodings are inef- ficient, which usually involve time-consuming graph query operations and need to re-extract the relative encoding from scratch for each target link, making them even become the main com- putational bottleneck for some methods (shown in Section 4.2).
Timestampe: fo <
Representation of A
Representation F
E2
and have the node mpressetations Relative encoding based on adjuvency
4
Eg
Link
C
(.FF.t
[0.0]
[0.0]
[0.0]
[0.0]
[1.1]
[0.01
[0.0]
[0.0]
[0.1]
[0.0]
[1.0]
[0.01
Figure 1: Without relative encodings, the learned node representations fail to capture the correlation between nodes. (For each link (u, v, f), the relative encoding here for node is [g(u, w), g(v, w) where g w) = 1 if there is an interaction be- tween u and w before t, otherwise g(u, w) = 0.)
To tackle the above issues, this paper makes the following three technical contributions. 1) A Unified View (Concept). We analyze the construction of existing relative encodings and find that they can be uniformly viewed as a function of temporal random walk matrices, where different relative encodings essentially correspond the construction of a series of temporal walk matrices based on temporal walk weighting. The presented function provides a unified view to analyze existing methods and may allow a more principal way to design new relative encodings. 2) Effective and Efficient Method (Method Design and Computation). Based on our analysis, we propose Time decay matrix Projection-basse based graph neural Network for temporal link prediction, named TPNet for short. TPNet introduces new temporal walk matrix that incorporates the time decay effect of the temporal graph, simultaneously considering both temporal and structural information. Moreover, TPNet encodes the temporal walk matrix into series of node representations by random feature propagation, which can be efficiently updated when the graph structure changes and is soorage-efficient Importantly, such node representations can be shared by different link likelihood computation processes decode the pairwise information, reducing the redundancy computation of re-extracting the relative encodings and avoiding time-consuming graph query operations. 3) Theoretical and Empirical Analysis. We conduct a theoretical analysis of the node representations obtained through random feature propagation. Our analysis demonstrates that these representations stem from the random projection of the proposed temporal walk matrix while preserving the inner product of different rows of the matrix. Moreover, we discuss the conditions under which random feature propagation can be applied to improve the computational and storage efficiency of other temporal walk matrices and provide the corresponding propagation mechanisms for temporal walk matrices of existing methods. Empirically, we conduct experiments on 13 benchmark datasets to verify the effectiveness and efficiency of the proposed method, where TPNet outperforms other baselines on most datasets and achieves a maximum speedup of 33.3 compared to the SOTA baseline. Detailed ablation studies also verify the effectiveness of the proposed submodules.
2 Preliminary
In this section, we will first formally define some important concepts in this paper and then give a unified formulation of existing relative encodings.
2

---

2.1 Definitons
Definition (Temporal Graph), A temporal graph can be considered as a sequence of non-o decreasing chronological interactions g = [(("1, ), (1) (fu2, (2) ....] with 0 S 4 S l2 S where (fue, (,,,4) (.) can be considered as a undirected link between u, and v; with timestamp 4, Each node can be associated with node feature 2u E Rdv, and each interaction (fu, v), t) has link feature C,.y E Rd where dy and dg denote the dimensions of the node feature and link feature.
Definition 2 (Temporal Link Prediction). The interaction sequence reflects the graph dynamics, and thus the ability of a model to capture the evolution pattern of a dynamic graph can be evaluated by how accurately it predicts the future interactions based on historical interactions. Formally, given the interactions before (i.e., {(fu', J"). tt) < <t)) and two nodes u, v, the temporal link prediction task aims predict whether there will be an interaction between and at L.
Definition 3 (K-hop Subgraph). We use the notation (tt) snapshot at t, where {t) includes all the interactions that happen before and ((t) includes all the nodes appear in ((). Besides, we defined the k-hop subgraph of node u as 9 (t) (V), (t), where 1ot (4) C (() is the set of nodes whose shortest path distance to u is less than on (t)) and (1) C (1) is the set of interactions between (L).
(V(t),((t) to denote the graph
Definition 4 (Temporal Walk). A k-step temporal walk W on G(t) is sequence of mode-time pair with decreased temporal order [6]. which can be denoted as W = [[w to), ... (w', tx]] with t= to t1 > ... tt and (fw; W++1) J. f4+1) is edge on (t) for 0 S i k 1. Figure 2 shows a visual illustration of a temporal walk. Here, we stipulate the first timestamp lg as the current time t to avoid undefinedness of to- We the notation M (t) to denote the set of all k-step temporal walks from u to u on G(t). Specially, M an (t) = {[(u, t)]} if = w and Ma... (t) 0 otherwise. When there is no ambiguity, we replace M (t) with M u,
2.2 Relative Encoding for Dynamic Link Prediction
2.2.1 Unified Framework
Given a future link (u, u, to be predicted, existing temporal link prediction methods (referred as node-wise methods) usually first learn the node representations h (t) and (t) independently, which are obtained by encoding their k- k-hop subgraphs,
he = Senc [c (C (1), u.k E,,,), hl,(() fenc (9t (1), c.k: x.e),
where u and & are the features of nodes and edges in (1) respectively" 2. The Sene here can be any encoding function that maps a graph into a representation such as a k-layer GNN with a pooling layer Then the link likelihood Pu., is given Pu,v = face (h.. (t., h. (t)). The face is a decoding function that maps the node representations into link likelihood such as an MLP with Sigmoid output layer. Detailed discussion about existing methods can be found in Appendix F.2.
As mentioned in the Section 1, learning representations independently might fail to capture the pairwise information of the given link. Thus recent methods (referred as link-wise methods) inject the pairwise information by constructing a relative encoding ="(((,,)) for each node ws E (t) U (t) as additional node feature (Detailed construction way for different methods will be introduced in Section 2.2.2). Then Equation (I) will be changed into
h (1) = Jenc (C) x u @ X u.
XE u,k,,
h1, Sen: (G) X.N
X
R e,k
E o.k):
u.k is the relative encodings for nodes in (t) and X u @ R features obtained by concatenating XN and R. Intuitively, the relative encoding (w,,)))) for each node w reflects its importance to predicted link (u, v, t), which can guide the representation learning process to extract the pairwise information specific to the predicted link from the subgraph. For the detailed construction way, the relative encoding r "(((.)))) is the concatenation of two similarity features w|u and "|y where r ulu "/ encodes some form of similarity between u/v and w (c.g.. the number of k-step temporal walks from u to w). Although the designs of similarity feature "0
where X.
u indicate the new node
a.kk
For memory- based methods (i.e, TGN). X represents the concatenation of node memories and features.
3

---

for different methods are induced from different heuristics, we find that they can be unified in function about the temporal walk matrix, which is
pll= 9([4 ( (t), A (t)), A
E s(W) for 0 0 k.
(3)
WEM.
The s(.) here is a score function that maps temporal walk scalar and A ( (t) denotes an i-hop temporal walk matrix whose each entry A is the sum of the score of all i-step temporal walks from to w. g(-) is function applied on the vector of (A..,.. (t), similarity feature. The above equation shows that each relative encoding implies a construction of the temporal walk matrix based on weighting each temporal walk (i.e., s(.)). Next, we will analyze
A. (t) e R++1 to extract
existing relative encodings and show how they can be represented in the form of Equation (3).
2.2.2 Analysis of Existing Methods
Our analysis focuses on the four representative link-wise methods DyGFormer, PINT, NAT, and CAW, which cover all the link-wis methods in the benchmark of dynamic link prediction [9].
DyGFormer [9]. The plls of DyGFormer is one-dimensional vector representing the number of links between w and u. For DyGFormer, we can first set the s(-) to be a one-const function
(i.e., sWW 1 in for any W), which will make (8) be the number of the k-step temporal walks from u to w. Then, setting g(-) to be a function that selects the second number of a vector (i.c.,
g( T1, ... xx)) x1) will make Equation (3) generate the similarity feature of DyGFormer.
PINT [8]. The "11" of PINT is a (k + D--dimensional vector, where r; we is the number of (i- -)-ppp temporal walks from u to w for 1 I i < & 4+11 1. Setting s(-) and g(.) can be set to one-const function and an identity function respectively will make Equation (3) outputs the similarity feature of PINT.
(k) and generates the w/ based NAT [7]. NAT maintains series of fix-sized hash maps 8 : ...., S0
on the hash maps. As proved in Appendix A. if the size of the hash maps becomes infinite, the "l is equivalent to a (k + 1) diddmmenioonal vector, where, for 1 < i S k + r = if the shortest temporal walk from u to w is less than i; otherwise, r; 10//u 0. Let h(-) be a binary function where h(x)= = 1 if x > 0 and h(r) 0 otherwise. Setting the s(.) to be one-const function and g(.) to function of g ([Iza .... ) (h( -== 3;)), 3;;,,(( ())
2:). -...
h(.)....... h(E 2;)) can make the Equation
(3) generate the similarity feature of NAT.
CAWN [6]. The similarity feature "11 of CAWN reflects the probability of a node w being visited when performing a temporal walk from u. Specifically, CAWN first samples set of temporal walks beginning from u based on causal sampling strategy. Then, for each node w, the similarity feature mll extracted based on its occurrence in the sampled walks. As proved in Appendix A.2, the simi-
larity feature "01" is the estimation of a (k + -i-dimensional vector, where, for 1 I S k 1, r, w/" is the probability of visiting w through (i-1)-sse -stepp temporal walk matrix based on the sampling strategy of CAWN, which can be represented as r,
-/vv = EweME- s' sWW). The value s'(W) for a given tem-
exp(-a(ti-ten -xp(-a((.-))) where a is hyperparameter to control the sampling process, Emg,,, ((fw', .w. 1 < 4)) the set of interactions attached to w; before 4, and expl exp(-a(ti--ea)
poral walk W = [wo,, 4o), (wi, (1) 41),.., (wx, (a:)] is defined as I ()
__(""..)).')EE.. can be considered as the probability
of moving from (w,, t.) to (wy-1.t(41) in the sampling process. Setting s(.) to s'(+) and g(-) to be an identity function can make Equation (3) generate the similarity feature of CAWN.
Conclusion. According to the above analysis, we can conclude that (i) Equation (3) provides unified view to consider the injection of pairwise information from the construction of temporal walk matrix, where different relative encodings (implicitly or explicitly) correspond to a kind of temporal walk matrix. (ii) Examining existing relative encodings from the unified view reveals their limitations. First, the relative encodings of existing methods (except CAWN) ignore the temporal information carried by each temporal walk, where their score function s(.) always yield 1 and the entries of the temporal walk matrix is just the count of the temporal walks. Next, although CAWN considers temporal information, they estimate the temporal walk matrix from the sampled temporal

---

Algorithm 1: Node Representation Maintaining (G.X.k,n,dR))
Timestamps: < < <2 <4
Initialize H H (k) RuxdR as zero matrix
4
2 Fill H with entries independently drawn from NO, 2
3 for (u, v, t) E g do
t
f2
(a) Temporal Graph ((!)
for /
do H (1)
+ at * H (1-1)) H H (5)
H (1)
41
Mt # H !!!!!
(1-1)
[(B (A.,,) (D. (F,,.) (b) A temporal walk on G(t)
Return H ..HH. H
Figure 2: A illustration of the temporal walk.
walks, which needs time-consuming graph sampling and may introduce large estimation errors. In the next section, we will present new temporal walk matrix to simultaneously consider the temporal and structural information and show how efficiently maintain the proposed temporal walk matrix.
3 Methodology
TPNet mainly consists of two modules: Node Representation Maintaining (NRM) and Link Like- lihood Computing (LLC). The NRM is responsible for encoding the pairwise information, which maintains a series of node representations. Such representations will be updated when new interaction occurs and can be used to decode the temporal walk information between two nodes. The LLC module is prediction module, which utilizes the maintained node representations and auxiliary information (e.g.. like features) to compute the likelihood of the link to be predicted.
3.1 Node Representation Maintaining
Temporal Matrix Construction. Based the Equation (3), designing a temporal walk matrix relies on the definition the score function s(.), where the element of a temporal walk matrix is
(1) Ewent. sW). Unlike most previous methods that only count the number of temporal walks, we consider the temporal information carried by temporal walk in s(.) to simultancously consider the temporal and structural information. Formally, let be the current time, given a temporal walk W- = [Wo, do), (wi, 41), (we, 4x)]. the value the score function s(W) -II e A(((-))) where À > 0 is hyperparameter to control the time decay weight. As the current time goes on, for each interaction (!w;, w5+1 1,4+1) in the temporal walk W, its weight e-t-tt+) will decay exponentially. The design of the score function is motivated by the widely observed time decay effect [1, 10] on the temporal graph, where the importance of interactions will decay time goes on, benefiting better modeling the graph evolution patterns. the following part of Section 3, the notation of s(-) and A (*) (t) will specifically refer to the score function and temporal walk matrix an identity matrix constantly.
proposed in this part. Besides, for A (0) (t), we stipulate
Node Representation Maintaining. Directly computing the temporal walk matrices is impractical since we need to enumerate the temporal walks and each matrix needs expensive O(n x n) space complexity to store. Thus, we implicitly maintain the temporal walk matrices by maintaining a series of node representations H (0) (t), (t),,, (R) (t) E R"xda, where dR < n is the dimension of
node representations and H (1) (t) E dd encodes the information about the I-step temporal walks beginning from u for < 7 < k. The node representations will be updated when a new interaction occurs. Specifically, we first construct random feature matrix P R xxdg, where each entry of P is independently drawn from Gaussian distribution with mean 0 and variance 1. Then we initialize dR (( (t) as P and H (t), (2) (t), ..., H (+)(1) (t) as zero matrix. When new interaction (u, v, occurs, for 1 < 1 1. k, we update the representations of u and v by
H (+)) H( (t) At H.. H( H( A (())
(4)
where the /- denotes the time right after 1. A pseudocode for maintaining the node representations shown in Algorithm 1. The maintaining mechanism here can be considered as a random feature propagation mechanism on the temporal graph, where we initialize the zero layer's representation
5

---

of each node as a random feature and repeatedly propagate these features among nodes from the low layer to the high layer as interactions continuously appear, The following theorem shows the relationship between the node representations and the temporal walk matrices.
Theorem 1. If any two interactions on temporal gruph G have different timestamps, the obtained representations H (0) (t), H (t),,, (h) (t) satisfy AAt (t) (t)P for < <IS k.
For simplicity, we assume the timestamps of the interaction are different, and we show how to update the representations when multiple interactions have the same timestamps in Appendix C. We leave the proof in the Appendix B.I. The above theorem shows that the obtained node representation the projection (i.e. linear transformation) of the temporal walk matrices, where the transform matrix is the initial random feature matrix P. The next theorem shows that the node representations preserve the inner product of the temporal walk matrices.
Theorem 2. Given any E E (0, 1), let ll -12 denote the L2 norm, dh denote ((1IA.
|| (t) and ( (t) denote e Ae (H (t), if dimension dæ of node representations satisfy
d 2 _ (33 1)m), then for any S u. v S n, and S &4,12 S k. we have
PP H (t),
(1),H())))0))) (1) - (A (b) (t) (() S d2 2
1
(5)
(k + 1)m
where (:,-) denotes the inner product and denotes laking absolute value.
We leave the proof in Appendix B.2. The above theorem shows that the inner product of the node representations is approximately equal to the inner product of the temporal walk matrices (i.e.,
( (t), ( (f)) x (A!! (t)). ! (t))). Specifically, given any error rate e, if the dimension of
the node representations satisfies a certain condition, the difference between (H! H (2))
(t)) and
(A!) (L)), A. (Ia) (1)) for any u, v, 1,,1,22 will be less than echi22 with high probability (2 1 (21-T
The error rate can approach O infinitely and thus the inner product of the node representations can approach that of temporal walk matrices infinitely, at the cost of increasing the dimension dR- As we will see in Section 4.3, a small dimension (< n)) in practice is enabled to make the inner product of node representations a good estimation of that of temporal walk matrices, Additionally, due to the i-th row of ( (t) being the one-hot encoding of i (since it is identity matrix), have (A) (0) (t)) = AlP,(t)). Thus, we can obtain [A4.) (t), ... Al (t)] in Equation (3) by calculating the inner product between all layers of u's representation and the zero layer of w's representation, expressed as [(FI,)) (t), H ()) ... (H. ( (()).
Remark. Compared directly computing the temporal walk matrices (I)),,, A (8) (1), which needs to enumerate the temporal walks and O((k + 1)m²) space complexity to store, maintaining the node representations largely improve the computation and storage efficiency, which only needs O((k- 1)ndR) space complexity to store and O(kdR) ) time complexity to update when new interaction occurs. Actually, Theorem
the direct result of Theorem based on Johnson-LLindenstruus Lemma [11], where the random projection can preserve the inner product and norm [12]. Notably, the method for implicitly maintaining temporal walk matrices via random feature propagation can be extended to other types of temporal walk matrices, provided they meet specific condition (i.e., the updating function of the temporal walk matrix can be written as the linear combination of its rows). This condition is not restrictive, and all the temporal walk matrices discussed in Section 2 fulfill We show their propagation mechanism and related discussion in Appendix D. In conclusion, the unified function in Equation (3), combined with methods of implicitly maintaining the temporal walk matrices, provides a new way to design a more effective and efficient way to inject pairwise information.
3.2 Link Likelihood Computing
Given an interaction (u, v,t) to be predicted, we compute its happening likelihood based on the obtained node representations and auxiliary features. Specifically, we first decode pairwise feature fa,.(()) from the node representations obtained in Section 1. Then we compute the node embeddings h,,(), (t) and (!) for node u and respectively based on their historical interactions. Finally, we give the link likelihood based on (1), (1), (t). For notation simplicity, we omit the suffix of h (t), (t), (t) and denote them as hus Nu, f fu,o in the following part.

---

Pairwise Feature Decoding. Although we can obtain the (k + 1) dimenssiona feature in Equation (3) by calculating the inner product between the zero-layer representation of one node and all layers of the other node's representation, this method does not consider the correlation between all layers of both nodes. Therefore, we use representations from all layers to decode the pairwise information. Specifically, we first take the node representation of u and from different layers,
e Akt " ((++1))dRR with * could be u or Then we concatenate them together to get Fu, [F. Fu] E [B2(++))xd and obtain the raw pairwise feature fu,e by computing the inner product among different rows of Fu,v, which is fu.. = Flat(Fu, (. with flat(-) means flatten matrix of [=((++))x((++1))) into vector of I2 [4(k++1²² Finally, we feed the raw pairwise feature fu,e into an MLP to get the pairwise feature fu.v, which is + 1)). The ReLU(.) here is used to reduce estimation error, where the inner product of temporal walk matrices should larger than zero and we thus set to be zero the inner product of the node representations is negative. The log(.) is used to scale the raw pairwise feature, where the range of the inner product between different layers varies greatly and the + the shift term to avoid the undefined value of log(O). We will see in Section 4.3 that these two operations can improve the training stability.
which can be denoted as F. je 10- H
fu.. (LoPllog(eeL((
Auxiliary Feature Learning. The auxiliary features such as link features also provide rich in- formation for modeling the evolution patterns of the temporal graph. In this part, we follow the previous methods [13, 9] and consider the auxiliary feature learning as sequential learning problem. Specifically, for node u, we take its recent m interactions S,, I(fu, wi ti).... (fu, Wm J fm) before L. and learn node embedding h. from this sequence. We first fetch the node features X.,N = [ma : .... m... E R.xddy and edge features X,,, = [e
[e m. e'm E R.xxde For timestamps, we map the timestamps into temporal features X..T = [o(t-41),.., ((t,(,)) E Rmxdr like [14], where ((t)) = [cos(w) At), .., cos( At) is time encoding function to learn the periodic temporal pattern. Besides, we construct a relative encoding sequence Xu.F
[fu.w ① fu.w...... fu.wm. @ fewuml E Rmx8(k+112 to inject the pairwise features, where fu.u.. denote the pairwise feature of u and Wm and @ is the concatenation operation. After obtaining the above feature sequence, we concatenate them together and feed it into an MLP to get the final feature sequence Z = MLP([X.... Xu,E, X
xx,rl) E Rxxd Subsequently, we stack layers of MLP-Mixer [15] capture the temporal and structural dependencies within the feature sequence, which is
~ = -0===---- 1 + W GW (1)
2 LayerNorm ()-)))
(6)
- 20 + W GeLU LayerNorm (())).
Finally, we get the node embedding by mean pooling h, = MEAN( The procedure to get node embedding he is similar and for the node that does not have m interactions, we pad the feature sequence with zero. Then, the likelihood of the link (u, v, t) is given by Pu,, = MLP((h.. h., fl, where MLP(-) is 2-layer MLP model with Sigmoid activation function in its output layer.
4 Experiments
4.1 Experimental Settings
We conduct experiments on 13 benchmark datasets for temporal link pre- diction, which are Wikipedia, Reddit, MOOC,, LastFM, Enron, Social Evo., UCI, Flights, Can. Parl., US Legis.. UN Trade, UN Vote and Contact. Eleven popular temporal graph learning methods are selected as baselines including JODIE, DyRep, TGAT, TGN, CAWN, EdgeBank, TCL, GraphMixer, NAT, PINT, and DyGFormer. Details about datasets and baselines can be found in Appendix F.
Datasets and Baselines.
Task Settings. The task settings strictly follow [9]. Specifically, we conduct experiments under two settings: 1) the transductive setting that predicts links between nodes that have been seen during training and 2) the inductive setting that predicts links between nodes that are not seen during training. Three different negative sampling strategies introduced by [16] are used to sample the negative links and the Average Precision (AP) and Area Under the Receiver Operating Characteristic Curve (AUC-ROC) are adopted the evaluation metrics. For dataset splitting, chronologically split
7

---

Table 1: Transductive results for different baselines under the random negative sampling strategy. blod and underline highlight the best and second best result respectively.
Metric
Dainset
JODIE
DyRep
TGAT
TGN
CAWN
EdgeRank
TCL.
GrophMMierr
NAT
PINT
DyGiformer
TPNer
Wikipedia
96.50...x 94.8
96.91. 96,45
98.76
96.17 1.
97.25
98.08
i5..
...
Reddit
98 31.. 96, 22 96. 02 98
99.11axm
91.80
97.53
97 21
99 19.13
99. 99.15
99.22
99.27
MOX::
80:23
81.97aa
85. 1
M1.16aa
27. 82.38
82.78
80.88
48
87.62
96.
LasPM
70.85
71.92
73.42 77.07
79.29
67.27
75.61
88.02,
20.06
93.00
94.50ga 04
Enron
S1.77-wax
82.38
-1.12--a- 86.53-L
89,56.xx
53.53.eas
79.70.am
82.25
90.60...aa
92
20.2s
92.47
92.90...z
Social Evo,
89.89
88.87
93.
x .3.57
21.96
71.95
93.13
93.37
93,33
92
91.42
91.73aa..
AP
UCT
89.4321
m
52.34gg
98.18ax
76-280an
80.07a
25
13.40a
93.79 16.44
93,
97.35
Flights
14.00
07.96
89.35 91,233a3
90.90
98.57
98.932g g8
Can. Purl.
09.26....:
66.54eame
70.70
20.58-2
63.82.2ax
64.55
68.67-2a
77.04.o.
79.72
06..36..44
97.36.s..
90,28
US Legis.
75.05 75.3duus 68. a 75.99
.0.58....
66.39
69.59
70.7d
78.71
71.85
71.11
10.58
UN Trade 64 64.94aa 63.21amx
61.47 65.03k.
65.
B0 00/41amms
62.21a3.
62.01
73.96a..0
70:20
66 46
87.2422
52.
22.21.. 65.72
m 52.81
58. cuss u1.90
70.45
06,
16.25
55. $5.55
75.12
Contect
46 31.1 95. 88 96 os 96.89
90.26 on 92 58 92.44a
91
92
97. 17.3
98 29
98.6620
Avg. Rank
7.85
8.77
8.54
10.54
8.31
3,69
3.15
1.08
Wikipedia
43 54
cs 96
on 58
95.54gx 90. i0 95.842 in
97.
77.72 1 UK. 162 is
98 21.1 co
99.30ga
Reddit
2 98.00ga
96.37
97.42
97.17
99.09aa
99.09
99.22 20.15
MOX:
23
65
87 11
91.21.i
81.38ax w. 80.86gn 83.12a1 1s
84.01
87.42a
90.55
87. 77 21
97.17
LasPPM
40
71.162t
11.50
78.47
85.92a3
83.77anas 64.06g:
13
86.92,a
80.28
93.06
94.39
Enron
87.96.eas
84.89
68, in 88.12-
90.45
57.05emas
75.74
54.38...x
91.68....r
92.87.xaa
93.53
93.98 24
Social Evo.
92,05
90.70
91.76.mm 95,39
87.5 81. 11.60
91.81.2a
86
28
90.8ti
96.16.
98.90
96.43
AUC
UCI
40-4420
68. 78.777x 78. 58 522.03..1 i 93.87axx
77.30amms
87.82.
91.81 81
92.31ax.7
M5.57
94, 29.4
26.792o.
Flights
96.21gr
14.13 58, 22g-
98.462x
90.223n
91.21
13.13
98,
11.00ge
88.80gg
98.
99.00ga
Can. Parl.
78.21
75.60 76.90
75.70
64.114ama
a2.46.a
63.17
84.04asus
a7
97.76
92.05
US Legis.
82.85 12.28
75.80-.. 83,31
77.16
62.57
76,27
76.96 76.90
85,
85.361saz
62. 12.10 10.
77.90
56.19
UN Trade .2.6 Masss 61.01.mm 69.10...
68.54ax
06.75
64.72am.
63.52
77.61.m
71.87
70.20ar.s
19.17
UN Vore 68-13 ss 67.1% 67.18g va 52, 80g in 20
83.00g> v. 62 12.977an 51.88gx
162
76.32aa
w 70.08gg ao
57. 57.12g
79.88ga
Contact
96.66.mm 96.48 96.952a 97.54
80.98
84.34amas
94.15
03.94
97.79
98.90
98.50amm
Avg. Rank
7.15
8.69
8.92
5.08
7.15
10.31
10.15
8.62
4.08
3,46
3,23
1.08
each dataset with 70% 10t///11%///// for trainingvaalidaringhhstinnn. The training and testing pipeline is the same as that in [9].
Model Configuration. For TPNet, the layer I of node representations. the number of recent interac- tions m, and dimension dg of the node representations are set to 3, 20 and 10 * log(2E), where E is the number of the interactions. We find the best time decay weight À via grid search within range of 10-4 to 10 Specifically, the best À for Contact is 10-4, the best À for MOOC, Can. Parl, and UN Vote is 10-5, 5, the best À for Wikipedia, Reddit, Enron, Social Evo., Flights and US Legis. is 10 the best X for LastFM, UCI and UN Trade is 10-?
Implementatoin Details. For baselines, we use the implementation of DyGLib [9], which is unified temporal graph learning library, and has tuned the best hyperparameters for each baseline. For baselines that not included in DyGLib (i.e., NAT and PINT), we their official implementation and find the best hyperparameters via grid search. Experiments are conducted on a Ubuntu server, whose CPU and GPU devices are one Intel(R) Xeon(R) Gold 6226R CPU @ 2.9GHz with 64 CPU cores and four GeForce RTX 3090 GPUs with 24 GB memory respectively. We run each experiment five times and report the average.
4.2 Performance and Efficiency Comparison
Performance comparison among baselines. The performance of TPNet and baselines is shown in Table 1. Due to space limit, Table only shows the results under the transductive setting with random negative sampling strategy and more similar results can be found in Appendix G. As shown in Table 1, TPNet achieves the best performance among all the methods on most datasets, verifying its effectiveness. Besides, the link-wise methods (CAWN, NAT, PINT, and DyGFormer) perform better than the node-wise methods, indicating the importance of injecting the pairwise feature. Compared to the baselines, TPNet simultaneously considers the temporal and structural correlations between nodes and encodes the temporal walk matrix into node representations with theoretical guarantees, which contributes to its superior performance.
Efficiency Analysis. We compare the relative inference time of different methods to TPNet to evaluate their efficiency. The results on LastEM and MOOC are shown in Figure 4 and more results can be found in Appendix G.2. As shown in Figure 4, TPNet not only achieves the best performance but is also more efficient than other link methods, where TPNet achieves a 33x and 7
8

---

Table 2: Ablation study results, where N/A indicates the numerical overflow er- ror.
Loath
VO0c
20% Jusiis
632
Datasets
TPNet
w/o
w/o Time
w/o Scale
93.6
MOOC
20
83 2e.s
94.62 94.622a.34
63.04
70.52 m4
94.30ga
N/A
Euron
22.90
83 23
92.86.a.r
N/A
UCI
97.302
88.70a.
97.19
73.
Legis.
80.58...2
69. 1...
71.83.a.a
70
930
UN Trade
87.24:0mm
62.56.na2
65.98-4.o
56.58
UN Vote
52.58
53.20
loga dirarree
Figure 3: Influence of node representation dimension.
speedups compared to the SOTA baseline DyGFormer and CAWN respectively LastFM. The CAWN and DyGFormer models utilize time-consuming graph queries (c.g.. temporal walk sampling) to construct relative encodings, which constitute the main computational bottleneck and consume over 70% of the running time. In contrast, TPNet caches historical interactions into node representations and constructs pairwise features based these representations, thereby enhancing efficiency.
Scalability Analysis. To further verify the scalability of TPNet, we generated a series of random graphs with average degree fixed at 100 and the number of edges varying from 1e5 to le8. Figure shows the change of running time and GPU memory of TPNet, where the growth the running time and GPU memory is close to and less than the linear growth curve respectively, showing the good scalability of TPNet. In contrast, PINT explicitly stores the temporal walk matrices and encounters out-of-memort error when the edge number reaches 1c7 (shown inAppendix G.3), verifying the impracticability of explicitly storing temporal walk matrices.
4.3
Ablation Study
Proposed Components. To verify the effectiveness of the proposed components TPNet, we compare TPNet with the following variants: 1) w/o NR that remove the node representations and the corresponding features that decoded from them. 2) w/o Time that only considers the structural information by setting the time decay weight À to be zero. w/o Scale that remove the log(.) and ReLU(-) in the pairwise feature decoding. As shown in Table 2, there is dramatic performance drop of w/o NR, which shows that the pairwise information carried by the node representations plays vital role in the performance of TPNet. There is also an obvious performance drop of w/o Time, which confirms the necessity incorporating temporal information in temporal walk matrix construction. Besides, the unreasonable poor performance of the w/o Scale is due to the various distribution of node representations across different layers, where, without scaling the raw pairwise features, the training will be unstable, and numerical overflow errors may even occur some datasets. Further details on the distribution of node representations from different layers are provided in Appendix G.5.
Dimension Change. To verify the influence of the node representation dimension. We vary the dimensions from 128 and report the performance of TPNet (denoted as TPNet-d). As shown in Figure 3, the required dimension of node representations is small, where only 1-dimensional and 16-dimensional node representations can achieve satisfactory performance on MOOC and LastFM respectively. For different datasets, we observe that the average degree may be main influence of the required dimension, where sparse graphs (like MOOC and Wikipedia) only need small dimension, and dense graphs (like LastEM and Enron) may require larger dimension. Empirically, setting the dimension to be 10 log(2E) enough to achieve satisfactory performance on all datasets, where E is the number of edges. Results on more datasets can be found in Appendix G.4.
Related Work
Temporal link prediction [17] aims at predicting future interactions based on historical topology, which is crucial for a series of real-world applications [2, 3, 18). Earlier methods considered the temporal graph as series of graph snapshots that are sampled at regularly-spaced timestamps [19, 20), which will lose the fine-grained temporal information due to ignoring the temporal orders of

---

100
100
10"
Running
20n
GPU
10'
Limer Growth
107
50
Baxtigg grocsiun
MAT
30
(4)
30t
100
10h
100
X0.2
XYA
70
75
10th
105
305
127
201
EDgus
Figure 4: Relative running time of different methods. The propor- tion of construction relative encoding time to all running time is marked in brackets for link-wis, methods.
Figure 5: Scalability analysis of TPNet on synthetic datasets with different sizes.
interactions graph snapshot. Recently, some continuous-time temporal graph learning methods have been proposed [21, 3, 14, 13), which consider the temporal graph as a sequence of interactions with irregular time intervals to fully capture the graph dynamics. For example, TGN [21] maintained dynamic memory vector for each node and generated node representations by aggregating memory vectors via temporal graph attention to capture the evolution pattern of the temporal graph. However, capturing pairwise information by merely aggregating representations of neighboring nodes [22] is challenging. To address this issue, the link wiie method was proposed, which constructs relative encodings additional node features to inject the pairwise information into the representation learning process [6, 7, 9. 8). For example, Souza et al. [8] proposed a relative encoding based on temporal walk counting and theoretically showed that constructing the relative encodings can improve the expressive power of models in distinguishing different links. Despite these advances, existing ways to construct the relative encodings still far from satisfactory, where computation efficiency a main concern and temporal information seldom considered. In this paper, we unify existing relative encodings into function of temporal walk matrices and explore encoding the pairwise information effectively and efficiently by temporal walk matrix projection.
6
Limitation
One limitation of our method is that the matrix construction approach requires manual predefined settings. Different networks may necessitate distinct construction methods, potentially leading to additional human effort in experimenting with various approaches. For instance, the proposed temporal walk matrix that incorporates the time decay effect may not optimal for networks characterized by long-term dependencies. Developing an adaptive matrix construction technique will be an interesting direction for future research.
7 Conclusion
In this paper, we study the problem of pairwise information injection for temporal link prediction. We unify existing construction ways of relative encodings into unified function, which reveals a connection between the relative encoding and temporal walk matrix. Then we propose a new temporal link prediction model, TPNet, address the computational inefficiencies and the ignorance of temporal information previous methods. TPNet introduces a new temporal walk matrix to simultaneously consider the temporal and structural information and a random feature propagation mechanism to maintain the temporal walk matrices efficiently. Theoretically, TPNet preserves the inner product of the maintained temporal walk matrices and empirically outperforms other link-wise methods in both effectiveness and efficiency. An interesting future direction may be designing an adaptive feature propagation mechanism.
Acknowledgments
This work was supported by the National Natural Science Foundation of China (No. 62272023 and No. 62276015).
10

---

References
[1] Petter Holme and Jari Saramäki. Temporal networks. Physics reports, 519(3)977-22,, 2012.
[2] Ziwei Fan, Zhiwei Liu, Jiawei Zhang, Yun Xiong, Lei Zheng, and Philip S. Yu. Continuous-tine sequential recommendation with temporal graph collaborative transformer. In International Conference on Information and Knowledge Management, pages 433-442. ACM, 2021.
[3] Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. International Conference on Knowledge Discovery & Data Mining, pages 1269-1278. ACM, 2019.
[4] Fan Zhou, Xovee Xu, Goce Trajcevski, and Kunpeng Zhang. A survey of information cascade analysis: Models, predictions, and recent advances. ACM Comput. Surv., 54(2):2:1-22736, 2022.
[5] Xiaodong Lu, Shuo Ji, Le Yu, Leilei Sun, Bowen Du, and Tongyu Zhu. Continuous-time graph learning for cascade popularity prediction. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pages 2224 2232, 2023.
[6] Yanbang Wang, Yen-Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. In 9th International Conference Learning Representations, 2021.
[7] Yuhong Luo and Pan Li. Neighborhoodd-wware scalable temporal network representation learning. In Learning on Graphs Conference, 2022.
[8] Amauri H. Souza. Diego Mesquita, Samuel Kaski, and Vikas K. Garg. Provably expressive temporal graph networks. In Advances in Neural Information Processing Systems, 2022.
[9] Le Yu, Leilei Sun, Bowen Du, and Weifeng Lv. Towards better dynamic graph learning: New architecture and unified library. In Advances in Neural Information Processing Systems, 2023.
[10] Giang Hoang Nguyen, John Boaz Lee, Ryan A. Rossi, Nesreen K. Ahmed, Eunyee Koh, and Sungchul Kim. Continuous-time dynamic network embeddings. In Companion of the The Web Conference 2018 on The Web Conference 2018, WWW 2018, Lyon, France, April 23-27, 2018, 2018.
[11] Sivakumar. Algorithmic derandomization via complexity theory. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 619-6299609000 2002.
[12] Santosh S Vempala. The random projection method, volume 65, American Mathematical Soc.. 2005.
[13] Weilin Cong, Si Zhang, Jian Kang, Baichuan Yuan, Hao Wu, Xin Zhou, Hanghang Tong, and Mehrdad Mahdavi. Do really need complicated model architectures for temporal networks? In The Eleventh International Conference on Learning Representations, 2023.
[14] Da Xu, Chuanwei Ruan, Evren Körpeoglu, Sushant Kumar, and Kannan Achan. Inductive representation learning on temporal graphs. 8th International Conference on Learning Representations. OpenReview.net, 2020.
[15] Ilya O. Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, Mario Lucic, and Alexey Dosovitskiy. Mip-mixer: An all-mip architecture for vision. In Advances in Neural Information Processing Systems, 2021.
[16] Farimah Poursafaci, Shenyang Huang, Kellin Pelrine, and Reihanch Rabbany. Towards better evaluation for dynamic link prediction. In Advances in Neural Information Processing Systems, 2022.
[17] Meng Qin and Dit- Yan Yeung. Temporal link prediction: A unified framework, taxonomy, and review. ACM Comput. Surv., 56(4):89:1 2024. doi: 10.1145/3625820. URL. https://doi. org/10. 1145/3625820.

---

[18] Le Yu, Zihang Liu, Leilei Sun, Bowen Du, Chuanren Liu, and Weifeng Lv. Continuous- time user preference modelling for temporal sets prediction. IEEE Trans. Knowl. Data Eng., 36(4): 1488-1488, 2024.
[19] Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural representation learning on dynamic graphs via self-attention networks. In WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining, Houston, TX. USA. February 3-7, 2020, pages 519-527. ACM, 2020.
[20] Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma. Toyotaro Suzumura, Hiroki Kaneza- shi, Tim Kaler, Tao B. Schardl, and Charles E. Leiserson. Evolvegen: Evolving graph con- volutional networks for dynamic graphs. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020.
[21] Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard. Federico Monti, and Michael M. Bronstein. Temporal graph networks for deep learning on dynamic graphs. CoRR, abs/2006. 10637, 2020.
[22] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. 2017.
[23] Roman Vershynin. High-dimensional probability. University of California, Irvine, 10:11, 2020.
[24] Moses Charikar. Similarity estimation techniques from rounding algorithms. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002.
[25] Ping Li, Trevor Hastie, and Kenneth Ward Church. Very sparse random projections. In Proceedings of the Twelfth ACM SIGKDD International Conference Knowledge Discovery and Data Mining, Philudelphia, PA, USA, August 20-23, 2006, 2006.
[26] John Wright and Yi Ma. High-dimensional data analysis with low-dimensional models: Princi- ples, computation, and applications. Cambridge University Press, 2022.
[27] James W Pennebaker, Martha E Francis, and Roger J Booth. Linguistic inquiry and word count: Liwe 2001. Mahway: Lawrence Erlbaum Associates, 71 (1(2001)2000) 2001.
[28] Rakshit Trivedi, Mehrdad Farajtabar, Prasenject Biswal, and Hongyuan Zha. Dyrep: Learning representations over dynamic graphs. In International Conference on Learning Representations, 2019.
[29] Peter J Diggle. Spatio-temporal point processes: methods and applications. Monographs on Statistics and Applied Probability, 107:1, 2006.
[30] Walter Rudin. Fourier analysis on groups. Courier Dover Publications, 2017.
[31] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings, 2018.
[32] Lu Wang, Xiaofu Chang, Shuang Li, Yunfei Chu, Hui Li, Wei Zhang, Xiaofeng He, Le Song, Jingren Zhou, and Hongxia Yang. TCL: transformer-based dynamic graph modelling via contrastive learning. CoRR, abs/2105.07944, 2021.
[33] Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? In Annual Conference on Neural Information Processing Systems, 2021.
[34] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Annual Conference Neural Information Processing Systems, 2017.
12

---

A Analysis of Existing Relative Encodings
A.1 NAT
(k) for each node u, which In Algorithm 1 of NAT, it maintains a series of hash maps 8u .... 8u sets of node ids. Next, will first prove the statement holds if the size of the hash maps is infinite.
(0)
Statement. 5(3) is set of nodes that u can approach through temporal walk whose length is less than +
Initially, the "! is set {u} and (2) .... interaction (fu, v). t) occurs and if the size of the hash maps is infinite, for < i S k, the updating function of hash maps can be represented as
( set empty The statement holds. When new
s = 0 U
- (((
where =0 and Sn denote the hash map after and before adding the interaction respectively. Then if the timestamp of (fu, v}, t) is larger than that of previous interactions, the newly generated temporal walks beginning from u must first visit through (fu, v}. (proved in Section B.1), thus the newly added nodes that u can visit through a temporal walk with length less than + 1 must belong to
Se (f-1) So (+) will contain all the nodes that can approach through temporal walk with length less than i 1 after adding (fu, t). The statement holds.
For node w, its similarity feature p is a (k + dimmenniioonal vector, where for 1 S +t, r; sr/u 1 w E a (f-1) and r w/u = 0 otherwise. Considering that the above statement holds, the similarity feature -01 is equivalent
(k +k+1 -)ddimensional vector, where ri w/u if the shortest temporal walk from to w is less than i; otherwise, r, mela
O.
Algorithm 2: Temporal Walk Extraction (G(t), k. u)
Initialize W to be (w,, ()):
2 for i.rom (Wip+tp) + the last (node, time) pair in W; Sample one (Lwp, w/) ),t') t') E Eugito with prob. x
do
exp(-a(1p - -()): W. < W; + (w',
6 Return W:
A.2 CAWN
For constructing ply, CAWN first repeatedly samples m temporal walks of length k begging at according to the sampling strategy in Algorithm 2. Then "/" is set to be (I- + 1)-dimensional vector, where wel will be the number of walks whose i-th visited node is for < < Ie 1, which can be represented as,
I
1
(8)
where W, is the j-th sampled walks and 1 =w is if [,[0]00 w; otherwise, 1w,k00] is O. Due to each temporal walk being sampled independently. 1w; [+]] 1 1...,:/000== [=]0=|= are m independent and identically distributed Bernoulli random variables Ber(Hge 1) where م is probability of reaching w from u after performing (i - 1)-step temporal walk according to Algorithm 2. And according to the strong law of large numbers (Theorem 1.3.1 of [23]), the mean of
these random variables (i.e., 1
m Σ Mwj + 1, ,,ll1)) will coverage to the mean as the
number of sampled walks m - co. The mean of the Ber( is 1-1 Expand all (i - 1)-step
temporal walks from to w, we have
1-1
Σ S(W),
WEMEN
13

---

Timestamps:
<2 </ L3 4
Historical interaction
New interaction
C3
4
l2
map
t
E4
4
13
B
Temporal Graph
New 3-step temporal walks
Previous 2- 2-step temporal walks
Figure 6: Illustration of the newly generated 3-step temporal walks beginning from D after adding new interaction ({C, (4) There a one-to-one map between AM and (14).
where f(-) is the sampled probability of walk according to Algorithm 2. For Algorithm 2, if we are current at (w,, (i), then the probability of moving to (wi+1, l441) through an interaction cxp(-a((,-(+11)
(fw,, w f++1) is proportional to exp(-a(t; ((+4)) which S(a exp(-a((;-))- Thus
the probability a temporal walk W = [[wp, to). (w,, 1 t1), .., (wa, tx) is
A-1
- (4+1)) (1wr, exp(-a(tt, - t²)) O=
S(W)
II
(10)
which the same as the score function s'(.) of CAWN we shown Section 2.2.2. Thus, ri (multiplied with a const ! is the same as EwEMt s(W)..
we/v
B Proofs
B.1 Proof of Theorem 1
The equation in Theorem 1 can be rewritten as (t) eait (t) We can con- sider eltt * (t) as new temporal walk matrix whose score function for a temporal walk [(wo, (WI, (1),.., myy (wi, 4:] at time is eitt s(W). Expanding it, we have
Mt sWW Att II
II j=1
Mt- C II AC
(11)
We use the notation (t) to denote e (t) and s(W) to denote eA s(W) for a I- step temporal walk in the following proof. The original problem transformed into proving that H (t) A (t) Note that for given temporal walk [(w,, to), (w1, (i,,tt,,... (wi, t:), each term of s(W) (i.e., I M)))) will no change as time t goes on. Thus the temporal walk matrices (t) will only change when new interaction occurs. Next, we inspect how the A (t) changes when new interaction (u, v, t) occurs. For each element ( (t), its change is caused by the newly generated 1-step temporal walks from i to j after adding the interaction (u, v, (). which can be written as
A0 - 20+++
Σ s(W),
(12)
WEAM,
where ++ denotes the timestamps right after and AM,, denote the newly generated 1-step temporal walks from to j. According to the definition of the temporal walk, the new I- step temporal walks must begin from u or v. Because if there is temporal walk that does not begin from u or v, can be represented as [(w,, .., (W,, 42), (u, f441), (v, f), (wi, 4))] or [(wg, fo),.., (w;, tz). (v, 1+))), t).,)... (wy, tt)).. which means that there is an interaction (fwe, u), (441) or (fw,, u), (141) whose timestamp t; is larger than t. (Since the timestamps of temporal walk are decreasing). This is impossible since (u, v, () is newly happened interaction. Thus only the u-th row and v-th row of the ( (L) will change. Besides for each newly generated temporal walk from u, must be [u, (), (v, L1) ... (wn, 4r))], where [(v, 11),-., (wi, 4))] corresponds to (l st-s temporal walk beginning from And for any (I - 1]-step temporal walk beginning
14

---

from we can add prefix (u, t) to make it become a 1-step temporal walk beginning from u. Thus for any 1 & i S there is one-to-one mapping between AM and (t) with M (t) denote the set of (I - 1)-th temporal walks from to before L, and we can rewritten Equation (12) as
(tt A (t)+ +
Σ e *((W)= (t, (t) te Ar * A (t),
(13)
WEM
The updating function for (!) is also similar. We give a visual illustration of the new temporal walks in Figure for better understanding. Finally, writing the update formula in vector form, for any 1 S I Is we have
(ct)= = (1) + eeC * ())
( = A (1) (t),
(14)
which is the same as Equation (14)! Thus if (t) = (1) 0 k. after adding a new interaction (u, v, t), for 0 < 1 - k (t+)- (t+)) still holds. Because we have
((+)
u (1) + ex H - (A) exx A (1)P ((t) (15)
Note that the equation in Equation (1) holds at initialization, thus the equation always holds and the theorem is proved.
B.2 Proof of Theorem 2
The Theorem 2 can be considered as special case of the Johnson--Lindenstrauss I Lemma [11], where the random projection [12, 24, 25] can preserve the norm and inner product. For the convenience of readers lacking relevant background, we follow [26] to provide the proof under the given conditions of this paper. We begin the proof by the following lemma.
Lemma (LLemma 3.18 of [26))). Let x E Ra be d-dimensional random vector whose entries are independent N(0, 4). Then for any E [0, 1},
èd
P [1| 1 c) S 2 exp(
(16)
8
The following part can be divided into 1) We first give two corollaries and their proofs. 2) Then we give the proof of Theorem 2 based on the corollaries.
B.2.1 Two Corolarries
Based on the above lemma, we can get the following corollaries.
Corollary 1. Given any E (0, 1), Rm Let P E Rdxm be random matrix whose entries are
independent (0, 4), if 2 log( ), we have
P ((1 <) | l2 < P 2 s (1 + ()
2 - 25
(17)
Proof. For the above corollary, we have
P - c) || < (1 + [
> 1 - 26
Px 2
P
> 1 - 28
||20||
(18)
P
IP
26
|
Note that each entry of P is an independent (0, 4). thus Px is random vector whose each entry
(Px);: E. PR. * x4 an independent. (0, | and each entry of T is an independent
d
(O, 1). Substituting it to Lemma and taking 2 log( ). have
Px 1/
2dd
P
>E < 2 exp
|
(19)
2
S 2exp(
* - logg ()(()) S 28
Based on Corollary we can get the following corollary.
15

---

Corollary 2. Given any m-dimensional vectors 21...., Zn. EE (0,1), let P PE& Raxm be a random
matrix whose entries are independent (0, 4). if d 2 / log(41/3)) n). for any 1 S i.j S we have
P (((Ps Pa.) - (I,, x3حي $ (1|0:112 + ||,,1
(20)
let E and E denote the event of { P((; + |, + و 11 S <|a;; + x,112ه and {|| P(#+ my)1l || x. |2 S < x; æ. ( respectively. Since a, + T.y and a. my can also be consider two m-dimensional vectors. Thus take and d 2 # log(11/3n) into Corollary 1, we have P(ET)) 2 1 - शमग and P( 2 1 전.ं Then let Ci, = Dig n Big denote that b and Big hold simultaneously, according the union bound, we have
1
P(Ct))=1-
=
21 (P (P(ET) +P(TT))
n (21)
where Eiy denote that E does not hold and Ety U Big denotes that E or Egg holds. According to the union bound, we further have
Oig) 21- 1- Σ P(C 21-11111 n² 1
-1 =
(22)
where Ciy denote that C. holds for any i,j and Uk, Ci, denote that there exist i, that Ctu holds. If Ct holds, we have
(1 <) |2 1 P(4: + m1))1 < (1 0| + 2,
(23)
e)|| - xz 1 P(x: - 21 (1 +)| 2,
(24)
Multiplying Equation (24) with 1 and adding it to (23), have
(Pr;, Pæ.) - (x) xz)) S 2
(l a + ||a5)11))
(25)
Thus we have
P P(,, Px;) (xi 2z)1 E (11=; 112 +1| 1|0x 21 1
P(OnsCiy)22 2
(26)
n
holds for any 1 < i,j n.
B.2.2 Proof based on Corollaries
The matrix of A (t) in Theorem 2 can be considered as n vectors with dimensions, where each row of A (t) is re-dimensional vector. Similarly, we can consider A (t), A (t) together as nok + 1) vectors with n dimensions. Considering that P E Rnxdæ is a random matrix where each entry is an independent (O,, 2 e-Ni * H (t) is the projection of A (t), substitute it into Corollary 2 and taking the number of vectors as (k + 1)n, we can get Theorem 2.
C Batch Updating Mechanism
For the situation where multiple interactions happen simultancously, we first compute each interaction's 's contribution independently and sum them together to update the node representations. The maintaining mechanism is shown in Algorithm 3, where packed the interactions that happen at the same time into a set and sum the independent contribution of each interaction in into A AH (k). For simplicity, we initialize A (1) ... A (k) each time and can be replaced by some efficient implementation such as scatter add operation in pytorch.
16

---

Algorithm 3: Batch Node Representation Maintaining (g (G.A.k,n,dR)
Initialize H H H(a) RexdR as zero matrix; ;
Fill O with entries independently drawn from (O, )
for E do Initialize AH (H( Ruxxa zero matrix
for (u, v, E B do
for
do
A AH AH (1)
+ e H (-11)
AH (1) AH (1) + eat H
for do
H H AH
10
11 Return H H H
D Propagation Mechanism for Other Matrices
For simplicity, here we only consider the situation where the timestamp of each interaction is different and we can adopt a similar batch updating mechanism in Section C handle the situation where multiple interactions happen simultaneously. For the updating of other types of temporal walk matrices, let (t) (t), A (*)(t) E (k+ denotes the concatenation of the temporal walk matrices. If the following two situations can be satisfied simultaneously. we can apply the random feature propagation mechanism to implicitly maintain the temporal walk matrices.
Condition After adding new interaction (u, v, t),, the change of each linear combination other rows, which is for each S i S n(k + 1), there exists ky,..., km and 1,,,,, bm satisfying.
be written the
A,(tt) = ki Ar, (1) + + Km Ar, (f),
(27)
where + is the time right after t.
Condition 2. After time moving At without adding new interactions, the change of each row can be written the linear combination of other rows, which is for each 1 S S n(k 1). there exists ki,..., km and li...,, Im satisfying.
A. + At) Aj
km Aim (t)
(28)
The motivation behind the conditions is that the projection is linear operation. If the node repre- sentations are the projection the temporal walk matrix at (I) = A(I) and updating function of the temporal walk matrix is the linear combination of other rows, then can apply the same updating function on Ht).. which will make H (t+) still be the projection of the temporal walk matrix. For example, applying (27) to H (t) will get
H k H (t) + (k1 (t) +... Ai A,,,
KR H (t)
(29)
A(t))P
Then we can ensure that H() is always the random projection of A(t) and thus preserve the inner product of the A(t).
D.1 Detailed Updating Mechanism
Based on the above analysis, we give the detailed propagation mechanism of methods in Section 2. For NAT, PINT and DyGFormer, their temporal matrix element A. (t) is the number of the (-step temporal walks from to e and their feature propagation mechanism shown Algorithm 4, where the obtained node representations
the projection of the corresponding temporal walk matrix.
For CAWN, its score function for temporal walk W = [(uro: lo), (wi, 4)..., (wr, 4)) is defined cxp(-a(ts-(wa)) as s (W) = [ Equí, el) exp( exp(-a(t,-) As time goes on, its element of temporal walk
17

---

Algorithm 4: Propagation Mechanism for DyGFormer (G.k,n,dR)
Initialize H H ((k) RexdR as zero matrix; ;
Fill ( with entries independently drawn from (O, )
for (u, u, G do
for 1 = to do
H Ha H (1-1) H H H (1-1)
Return H H (K;;
Algorithm 5: Propagation Mechanism for CAWN (...kk,m.dzz))
Initialize H (1),, (k) Rnxda zero matrix;
Fill H with entries independently drawn from N(0, d.
3 Initialize d IR" as zero vector;
Set (prev E IR to be zero;
5 for (u, v, () E G do
d d exp( at tprev)):
for
do
H (1)
J.
du
H (1)
+
dot1
H (1-1)
H (1)
dy
H (1)
H (1-1)
d.11
dut1
10
d, = du + +1;
11
d, = d2 +1;
12
Eperr = t:
Return (0) H (1)
H (k)
13
matrices will not change. When new interaction (u, 6) happens, for a temporal walk matrix A ( (t), its u-th row and v-th row will change. Formally, let d(t) E TR denotes a time decay degree vector, where for each node u, (t) is defined dt) "((u..))))),, exp(-a((' ()) with Eu, denoting the set of interactions attached
before t, then the updating function the temporal
walk matrix A (k) (1) can be represented
du(t)
( + 1
(
dz(() +1
dy(() +1
(30)
( d,())
4 (t) (t) + (t) +1 * A (t),
+1)++
where d.(t)
2,00)+ A (2)
(f) corresponds the change in score of the old I-step temporal walks begging
from u and 2,00)I * (!-))) (t) correspond to change caused by the newly generated (-step temporal walk from (the same for and similar analysis about the updating of temporal walk matrix can be found in Appendix 1). Then we can give the propagation mechanism for CAWN in Algorithm based on the above analysis, where d corresponds to the time decay degree vector.
E Broader Impact
proposed an effective and efficient temporal link prediction method, which may advance real- world scenarios that rely on link prediction as a cornerstone, such as recommendation systems. For potential negative impacts, overly accurate link prediction in some contexts may lead imbalanced outcomes such reduced diversity in recommendation systems.
18

---

Experimental Settings
F.1
Datasets
Experiments are conducted on the following 13 benchmark datasets 3 collected by [16].
Wikipedia is bipartite interaction graph that records the edits Wikipedia pages a month. Nodes represent users and pages, and links denote the editing behaviors with timestamps. Each link is associated with 172-dimensional Linguistic Inquiry and Word Count (LIWC) feature [27].
Reddit bipartite graph capturing user posts under subreddits over month. Nodes represent users and subreddits, while links denote timestamped posts. Each link carries "72-dimensional LIWC feature.
MOOC is bipartite interaction network of online courses, where nodes represent students and course content units (e.g.. videos, problem sets). Links indicate students' access to specific content units and have a 4-dimensional feature.
LastFM is bipartite network detailing song-listening behaviors of users over one month. Nodes are users and songs, and links represent listening activities.
Enron records email communications between employees of the Enron Energy Corporation over three years.
Social Evo. is a mobile phone proximity network tracking daily activities within an under-
graduate dormitory for eight months, with each link having 2-dimensional feature.
UCI is an online communication network with nodes representing university students and links representing posted messages.
Flights is a dynamic flight network showing air traffic development during the COVID-19 pandemic. Nodes represent airports, and links denote tracked flights. Each link has weight indicating the number of flights between two airports per day.
Can. Parl. a dynamic political network recording interactions between Canadian Members of Parliament (MPs) from 2006 2019. Nodes represent MPs from electoral districts, and links are formed when two MPs vote "yes" on a bill. The weight of each link represents the number of times one MP voted "yes" in support of another MP in year.
US Legis. is senate co-sponsorship network tracking social interactions between US Senators. The weight each link indicates the number of times two senators co-sponsored bill in given congress.
UN Trade captures food and agriculture trade between 181 nations over more than 30 years. The weight of each link represents the total normalized agriculture import export values between two countries.
UN Vote records roll-call votes in the United Nations General Assembly. link between two nations increases in weight each time both vote "yes" on item.
Contact tracks the evolution of physical proximity among approximately 700 university students over month. Each student has unique identifier, and links indicate close proximity, with weights revealing the extent of physical closeness between students.
The statistics of the datasets are shown in Table 3, where #N&L Feat stands for the dimensions of node and link features.
F.2 Baselines
We select the following eleven popular baselines:
JODIE [3] designs recurrent architecture to maintain a memory vector for each node and projection layer to map the node memories into future representation trajectories.
Dy Rep [28] considers each link as temporal point process [29] and designs a deep temporal point process model to capture the dynamics of the observed process.
http:://eendd.orr//eood/////2111 http://22377991.11c0886883330
19

---

Table 3: Statistics of the datasets.
Datasets
Domains
#Nodes
#Links
#N&I. 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 month
669,065
Unix timestamps
MOOC
Interaction
7,144
411,749
&
True
17 months
345,600
Unix timestamps
LastFM
Interaction
1,980
1,293,103
&
True
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 years congresses
Can. Parl.
Polities
734
74,478
&
False
14 years
14
US Legis.
Polities
225
60,396
&
False
12 congresses
12
UN Trade
Economics
255
507,497
&
False
years
32
years
Vote
Polities
201
1,035,742
&
False years
72
years
Contact
Proximity
692
2,426,279
& False month
8,064
5 minutes
TGAT [14] proposes time encoding function based on Bochner's Theorem [30] and combines it with the graph attention mechanism [31] to learn dynamic node representations.
TGN [21] proposes general framework for temporal graph learning, which includes memory module to maintain node memories and an embedding module to aggregate node memories.
CAWN [6] captures the evolution pattern of the temporal graph by causal anonymous walks, For a given link, CAWN first sampled set of temporal walks beginning from the two end nodes respectively and constructs relative encodings. The sampled walks together with relative encodings are then mapped into node representations via a sequential model.
EdgeBank [16] is statistical method, that gives the likelihood of link based on historical interactions between the two end nodes.
TCL [32] propose graph transformer architecture [33] learning node representations, which samples neighbor nodes based on BFS and maps them into the node representation.
NAT [7] propose a dictionary-type neighborhood representation to efficiently capture the correlation information between nodes, which maintains series of N-caches to store the neighborhood information and use them decode the pairwise information between nodes.
PINT [8] proposes an injective temporal message passing mechanism to learn node repre- sentations and relative positional features constructed based on temporal walk counting to inject pairwise information between nodes.
GraphMixer [13) proposes a simplified temporal graph learning architecture, which em- ploys MLP-Mixer to learn the representation of node from its historical interaction sequences.
DyGFormer [9] proposes transformer architecture [34] to learning node representations, which include a patching technique to capture the long-term histories of a node to and a neighbor co-occurrence encoding scheme to capture the correlation between nodes.
G Additional Experimental Results
G.1 Performance Comparison
The results under other settings shown in Table 6, Table 7, Table 8, Table 9 and Table 10.
G.2
Efficicency Analysis
Efficiency analysis results on Reddit, UCI, and Wikipedia are shown in Figure 7.
G.3
Scalability Analysis
The scalability analysis result of PINT is shown in Table 4, where 00M indicates the oft-of-memory eπrоr.
20

---

TIM DOLSRO
MO0 200-ogoorooo proct.nn
133.25
Aver prectrm
TOP
TOM
90
X586
X33
8
TOL
10
10 Lime par opoch
10
10
Relative time per spech
pur apach
Figure 7: Efficiency analysis on more datasets.
Table 5; Average norm of node representations from
different layers.
Dataset
Layerl
Layer2
Layer3
Table 4: Scalability analysis of PINT.
Wikipedia
1.16E+01
1,23E+03
2.06F+05
Reddit
4.28E+01
2.52E+05
2.54E+09
PINT
MOOC
5.70E+00
2.50E+03
1.52E+06
Edge Number
LastFM
9.64E+01
1.81E+04
4.78E+06
Time
Memory
Enron
2.73E-01
1,50E+00
4,60E-02
100000
51.18
92.32
Social Evo.
2.81E+03
7.30E+06
1.56E+10
1000000
594.77
2175.80
UCI
1,88E+01
8.67E+02
6.27E+04
10000000
N/A
OOM
Flights
3.38E+01
8.12E+03
3.29E+06
100000000
N/A
OOM
Can. Parl.
8.36E+00
7.49E+02
1,40E+04
US Legis.
4.39E+01
2.75E+03
1.22E+05
UN Trade
1.67E+022
1.58E+04
1.04E+06
UN Vote
2.41E+02
3.36E+04
3.22E+06
Contact
9.88E+00
8.83E+02
9.36E+04
G.4 Influence of Node Representation Dimension
Results on Wikipedia, Enron, and UCI are shown in Figure
G.5 Statistic Analysis of Node Representations
Table 5 shows the mean of node representation norm at different layers, where aEb indicates a x 10a.
21

---

podia
Eraon
UC1
20300
5014 Boceiit
33.0
50th Basile
SOTA Iaaslre
32.0
$2.0
Aeeroge greet
20
77.00
22.0
14.05
Figure 8: Influence of Node Representation Dimension
Table 6: Inductive results for random negative sampling.
Metries
Dalnsets
JODIE
DyRep
TGAT
TGN
CAWN
TCL
GruphMixer
NAT
PINT
DyGFormer
RPNei
Wikipedia
94.82-.a:
92.43 96.22...r
97.88-aa1
98.24-s.a
96.65
98,
Reddit
06.50)a1s 96.08ar-a 97.09
97.50 ar 98.62ga.
34.09
96 26
28.24
98.56..m
98. 84.84
2m.
MOOC
79.63 a1.07 85.50 89.04
81.42
80.60
81. 11.1
83.62 ...4
87.90
95.07 86.96
LasUJM
81.61e14 81.02.5. 78.63
$1.45
80.42...
73.53s1.
82.11
92.24
92.42...
94. 94.23
23.3
Enron
80.72a:
a 74.55 x 67.0521
77.04g
86.35
76.14
75.88
87. 18
88.1220
89.76
90.34ga
Social
01
91.41ama
80.77
79.94
91.86...
87.44....
92
14.14
93.24
UCI
70.86g: 57.4821 79.54gm
68.
92.73
87 87.36ga ox
91.192m
87.31
94.72
94.542o
95.74ga.m
AP
Flights
94.74 92.88
73.73
96
oz
83.41lao
20.03
96.742
97 07.64.20
77.702mmm
97.97
Can. Parl.
53.92 54.02as
58.18
54.10
55.80 54.302n
55.91
50.32 61.90
87.74gm.
68.00
US Legis.
54.93
i 57.28am m 51.00ga
68.63
53. 17
52. 02.50gm
20.71
60.41
19.71 s
54.28
61.71
Trade
59.65 57.02.s.c
58.31aam
65 25.2.
12
62.17
09.57
60.37
61.50a
86.53
UN Vote
56.64g
54.62g
52.24g
58.85ga
40.94g
51 60g
50.68
60.
57.43..
55.93go
58
38.00ga
Contact
94.34a 18
95.87
98.82
111
90.50.mo.
12
97. 27.41
08
98.39
Rank
7.62
8.69
7.92
6.15
6.15
8.46
7.85
4.69
4.15
3.00
1.23
Wikipedia
91.33
91.49
95.90.
97.72
98.03
95.57 i0
96.30
95.5
97.76
98. 18m
98.90.
Reddit
96.52
98.05
96.98
07.30
98.42.s.a 93, or
94.97 sms
08.00)
98.38...r
98.17 38.71
MOOC
83.162: 84.002::.
16.842o11
91.24
81.86
81 43
82.77
84.72
90.27
37.62
95.55
LastFM
81.13 82.24...:
76.99.w.
82,61-a4s
87.82
70.84.a..
80.37
91. 01)60)...
22.15.ma
91.08
95.36
81.96g: 76.3424m
64.63
28
87.02g
72.33
76.51
87.05
87.97 20
90.69
90.21
Social Evo.
03.70 11.18
93.41
93.43
84.73
93.71an
94 04.0020or
88. 16
94.78
96. 25.20
95.47
AUC
UCI
78.80gma
58.08
77.84
as
90.44gamm:
84.49
89.30g
83.78
93.18
92 63333mm
94.40
Flights
05.21
93.56am
86. 36
96.922
96.86gs
82.48
82.27200
96.97
07.002oms
27.00
98.052a.0
Can. Parl.
53.81auas 55.27
56.51..mm
55.86
58 83.....
55 om
58 32
62,70
19.61.mm
89.3319.4
69 69.21:1a
Legis.
a 61.07a
2m 02.38
11 50.43
27.20
64.22
61 20
53.21
29
UN Trade 02 02.28 58.82ar.s
62,
72 59.90
67 06....
63. 76
63. 4810
00
10:2.1
64.062em
G7 2511
86.88
UN Vote
58.13
$3.13
51. $1.83 a. 61.23 am 18.31
30.51 1.s 50.01.0m
68.55
lase
50.01
56. 33..e
51.82 cm
Contact
96
91.89a
96.532o
04.84 80.07
93.00zooo
82.83
90.70
97. 17.0022.1
98.30
98.51280
Avg. Rank
7.46
8.62
7.92
5.69
6,46
8.77
8.00
4.77
3.92
2.77
1.62
22

---

Table 7: Transductive results for historical negative sampling.
Metric
Dataset
JODIE
DyRep
TGAT
TGN
CAWN
EdgeBank
GraphMixer
PINT
DyGFormer
TPNet
Wikipodia
63.01....
87.38
86.80
71.21-14
70.35
89,05...
50.90....
08.36....
91.33
81,55-1. .2.23....
Redlit
80,03...
7..83....
21.22
77.1
78.
80.58....
81.57 a3
...
MOOC
78.94 a5
k2.19...
87.06....
74.05-mm
60.71
77.06.nn
77.77.m.0
65.42-..x
-1.80-
85.85
92, 09.09
LasFM
71.35
76.87
69.86...
73.05
59
72:47
78.75...
81.95
81,57
87. 87.74...a
Earon
60.85as. 1s
64
64.73
1 76.
03
70.00
77.98
72.90. i
25
.0.70....
Social Evo.
87.48 93.29
95.01
85.53
80.57
91.7dinn
91.93
99.29...
98.73...>
97.38
90. 10.80....
AP
Flights
UCI
06.4842.3
75.29as. 15
67.01-
72.38-
80.48as.u 63.30...
06.70
64.72-aar
70.53
50
70.88.
80.25
71.47
84.11ara
35.38
04.74...3
23.96
06.82-1.4
06.39...a
12.17
86.34
00.10-1-7
Can. Parl.
63
68.421sur
60.53
63.8
65.98
71.3
17.72...s
63.8
27.00
50.0
Legis.
11.772xmm m 85
62.
74 14.00gmm
68 89282 63.222xx
80.532+
81
11.12 on 73
28.882a 1s
85.30g1
54.55
UN Trade 61 19... 59.19
50.74iem
58 3i.aa
55.
$1.
.5.90
57 15
78.65....
70.07
61.11....
85, 25.2
UN Vote
70.022
60.30
60
51 e1
84
32.30
71.30
71.7
14
Contact
36.31 96.39
96.05
53,05
80.16....
85,
sa 93.50...
93.30
96.81
97.01.xae
97.57 k.om
98, 02.022 i..
Avg. Rank
8.23
7.69
7.54
5.92
10.31
8.08
7.77
6.23
5.85
3.62
4.25
2.46
Wikipodia
s0.77 77.70
82,87
62.7d
67.81.
85,70
87.68..ar
09.32...
89.25 t0.ce
78.80...e
70.89
Redlit
80.52ae 80.152e
79.33ax
81.
81.112x09
20
78 0
76.40200
77
79.36. 19
82.9820m
80.54
MOOC
82.75 $1.00..m: 80.81
28.00
71.57-1.r
61.90
w2.09.w.
76.68...
64
a7.40
67.0
93.
LasFM
76:22as. 76.05.1
77.07a
67.88.0
78.
78.00
47.24
61.21
75.80
81 10
78..8
84.64
Earon
75.394s.m
74.09-aas
77.09.s.:
65,10-ea:
79.59
67.95.w..
75.27-2a4
73
22
83.80
70.35-
81.16-122
Social Evo,
90.06as.us
98.12...s
08 us
91.71 87.43
85.8
93,4
94.39ax
11.87
96 2..
97.28
07. 27
AUC
UCI
78.642x so 57.91
80
77
77.255g 57.86
60.541gx
72.25
77
T1.32g
92.066o
76.97
80. 80.42
Flights
68.97am. 69.18aumx
68.39
66.11....
74.61imm
70.57
10.57
67.11
69.52....
71.82 uasa
Can. Purl.
62.44
70.1621 n3 70. 11.6622>
73.20ax
72.06za s4 63 63.04
60.962a
79.0331m
81.47270
73:80 s
97.61
M6.W
US Logis.
67.47
91.41-aaa
73.47
83.5
78.62
67.41imm
13,97
85.17
91.63...
83, $3.45
90,77
96,28
UN Trade
68.92 4
60.37
63.08
63.000.. 14 86. 66.6
61.432
63.28
80.68...s
73.86..
88.90
UN Vote 76.84g
74.72g
53.952s
73.40zx
51.27
K0.62ge.n
52.28g-m
62.61g1
76.47.
26.01
64.27
78.43g1
Contact
96.35
96.00a
86.39
98.70
83.06
92.17a
95,31awa
98.1daxas
86.79
97 97.30
97.17ax
97.73
Avg. Rank
6.77
7,31
8.38
5.62
10.31
7,54
8:54
7.08
6.46
3.15
4.77
2.08
Table 8: Inductive results for historical negative sampling.
Metrics
Datasets
JODIE
DyRop
TGAT
TGN
CAWN
TCL
GraphMixer
NAT
PINT
DyGFormer
RPNet
Wikipedia.
68. 18.69
62.18
81
81.76iam
67.27
82 20.....
87.00
17.37
28.22
71-12
21.28.1.0
Reddit
62.34
61.60
63.47-..
64.85
63.
20.83....
64.50
61.5l.m
m7.
65.37
62.15-
MOOC
63.22....
62.93
76.73
77.07
T168
71.27
71.00
69.30...
80.82
81.85
LasFMM
70.39. 71.45...
76.27-
66.65.e
7L.33
65.78...m
76.12
70.21
77.96-:aa
76.35
82.27 =..27
Enron
85.8621m:
62.08
61.40..m
62.91
60.70
67.11
72
62
80.47
67.07-1
74.60-:
Social Evo.
88.01ar 88.722) in 93.97
90.6621
e
79.832
94. 10 a
94.01a0
84.892
o 96.7621 i
96.
36.38..1
UCT
63.11 52.47
30
70.782m
64.54
$1.66
51.56
85.49
78.48.: 12
Flights
41.012::4
62.832 a
64.72.>..
50:31g
56.822
64 5..00
65.2826
65.
51.63321
n 53-46
57.11 i
54.67 m
Can. Parl,
52.60 12.28
56.72....r
54.42
57.14
56.71
55,84
61.561s.s
50.61a..
87.40.0.
US Legis.
52.94.za: 62.10
51.83
61.18
55.56
53.87
52.03
64.61
58.37
56,31 2.3
66.95
UN Trade
55.46 45
55.28-am
52.80
55.00
as
54.04gma
70.04
50.20
7..83
UN Vote
61.044..as 60.22
53.05
63.74
47.98
21.19
18.09
64.9....
65.75
52.63
65.24-..a
Contact
90.42
20.22
94.15 as
13
74.20
40.44
80.91
84.13
90.68
90.56
30.50
Avg. Rank 7.46
7.62
5.69
6.31
8.08
5.92
5.23
7.62
4,23
4.62
3.15
Wikipedia 61. 86 67.042 v 78 18.38
75.
02.042.
79.70
82.872m
40.9024 v
73.20
06.33 m
G7 07.9022
Reddit
.1.69 60.45
61.13....
61.55....
61.94
68..
61.27
58.33
61.02...
61.81
62
MOOC
61.23
74.08 s..
77.69
7L.68
69.82
72.53
67.99....
75.92
80.77
84.46
LasiEM
48
68
09.89....
66.99....
....
70.07
61.88...
72.02
70.73
77.10.ww
Enton
65.32 61.50
57.84
62 62.68....
62.25
61.06...z
68.20
61.69.....
78.90
65.78
74. 50 .0
Social Evo.
88.53
87.93 on
=1.87
92, 10
63.54grax
83.62
84.80
m
96.91gmm
AUC
U:C
60.24g-
51.25
62. 02.32gg1..
62.09ga
50.30ge
70.46
70.98
42.502m
81.34ga
66
71. 3..30
Flights
60.72
61.99a1
63.08-a.2
50.66
56.58
63.
63.50
48.39..
49.76
56.05
50.08
Can. Parl,
b1.62g
52.382a
58. 30.00
05.64ga
60.11ge
67.30=
56.882
61.72,
48 48.932
88.68g
69. 11
US Legis.
58 18.12 67.94
19. .9..9
64.87
54.41aan
52.12
19.28
66.961..>
62.88
62.82
56.07=>x
68.37
UN Trade
58, i3..x
57.
59.74
35.61iass
60.95
61.12
59.58
70.13
62:61
58.46
80.70
UN Vote
86.16
51. 73.... 68.59
48.01
54.66
45.19
67
07.60
69.47
50.85-2.
65.75
Contact
80.80
88.88
93.76
88.81
71.79
90.37
90.0
8171..a
91.99
94.14
93.47
Avg. Rank
7,23
8.08
5.92
6.00
7.46
6.00
5.38
7.92
4.31
4.38
3.31
23

---

Table 9: Transductive results for inductive negative sampling.
Metric
Dataset
JODIE
DyRep
TGAT
TGN
CAWN
EdgeBank
GraphMixer
PINT
DyGFormer
TPNet
Wikipodia
75.65 70.21
87.00.a.
85.62
74.00/2az
50.63...
86.70
50.85
m2.39-
79.35- 28.29...
Redlit
08.98
26.30... 29.
88
10
a1.07
85.48
87.45
85.26
a1.7
87.50...>
18.19...
MOOC
65.23 61.00-.m 15.96-244
27.50
73.51.mm:
49.43
74.88.ms
74.27
77.28....
75.70-..4
81.24.
88.18-
LasFM
62.67
71.13
65.95
67.18
75.49
58,21
68.12
6102....
72.24
13.97...
77.99...
Earon
68 0 67
63.94
04
m0
75.15
73.8
71.28
75.01.m.
70.34a: n 20
77.4)amm
16.36.1
Social Evo.
89.82
93.28
91,81-244
96,
13...
88.32
83.69
91,90.mn
91.72
12.12.
97. 15.
97.68
97.35
AP
Flights
UCI
65.99aa.
09.07.4.m
70.57
15.48-.2x
68.67
70.94amm
71.09vam
61.61a..
09.18-...
81.08-e.e
67.43 76.
74.02
a0.
74.87
57.55
19.16...
61.99-1.0v
70.92..m
72:25a..m
64.78
Can. Parl.
48.42 58.01avss
08.82...
65.31
67.
67..5
62, 16.
65.80
69 09.88
18.05
59.15
95.44
85.59
Legis.
10:27 83 is 61
67
65,81
64 04
78. 1 79 m3
88
67.
07.7824 m
81.25
91.05
UN Trade 60. 30.42 60.19 00.
61.01xxmm
62.5di
72.97
61.00
60.15
78. 18.38
69.72...:
55, 79
86.61...m
UN Vote
. 67.53
67
63
32.19
50.62
72.33
68.37a1
a1
05.052141
Contact
93. a3... 9t.18.wax
.4.35
98.18
89.31.so
85, k0.
91.35..a
40.87
91.13 13..a
91,05-aa
94.75
95.84-a..
Avg. Rank
9.08
8.62
5.92
6.23
7.62
7.77
6.69
6.38
7.31
5.08
4.16
2.85
Wikipodia
70.90
80.97
20.95
81.
s2.10
84.28
52, 11..0
75.09 77.03....
75.36
Redlit
83.5 35 82.90
84
24.50
88.04ga
85
00
84.07
76.01.:
81 s
86 23
81.64
MOOC
66.63
63.20....
13.18
77.41....
70.32....
18
w0.
72.45 25..5
75.56.
27.00....
60.76.
89.07....
LasFM
61 12. 62.15 1z
23.99
65.461x.
67 92
77.37am.
46.98a.
60.222x..
58 68.54
69. 30.51...
69 69.25
72.48.0.
Earon
70.92
68.78-1ax
600.5-222
7L.3t
75.17
75.00
67.04:mm
71.58....
09.62...u
78.91
74.07
75.1
Social Evo,
90.01as.>
98.07
22.94
96.24
89 89.98
87 18.8
93.4duwr
94.22
92 12.53....
97. a7.
a7.51
un.s
AUC
UCI
64.14g)
54.25ga
60.80g:
64
38.0622
58 0032
70.0621 es 74
74.50gg
49.
79.42goo
66 061
70
Flights
60.99
71.13...>
T3.47am.
6.......
69.70
81.10a...
72.5dawa
72.21
59.73
59.01...>
69.58
66.21
Can. Purl.
52.89
63.5822
72.4721
60.57amm
72.932 1
61.41
60.472
70.522 w 80.03;
65.302x
96.702m10
86.06..mm
US Logis.
59.05
89.d1.wm.
71.62-s4a
76. 18.12
68, 08.66
82.5dia.
81.22
98.01..a5
79.09.s.a
87.96....
94.48
UN Trade
66.82a 65 66.
66.37
71.78am
74.20ax
67.80)..
66 53
80.77
75.70
62.30
12.36....
=9.56
UN Vate 73:73z>
72.80ga
13.04g
72
32.70
72.85
52.02. u 51 80
17.36;
74.11gm
53.37
79.13g
Contact
91
96.23a
44.10
91
11.6
37.68
85.87
91.28,u..
90.96
92.51
94.71ara
95.01
95.93
Avg. Rank
8,08
8:23
6.77
6,31
7.31
7,00
7,00
6.54
7.46
5.08
5.00
3.23
Table 10: Inductive results for inductive negative sampling.
Metrics
Datasets
JODIE
DyRop
TGAT
TGN
CAWN
TCL
GraphMixer
NAT
PINT
DyGFormer
RPNet
Wikipedia.
38.70
62.19
81.77imm
67.24
82 20....
87.00
17.37
78.23
71-12
71.29....
Reddit
62.32 6l.
63.40
64.84.am
63.65
60.81
69
61.5
67.
65.35-
62.14 14
MOOC
63.22.... 62.92.s:
76.72
77.07
71691
21.28.....
73.99
69.30...
80.82
81.85
LasFMM
70.39. 71.45...
76.28-
60.46.4m
7L.33
65.78...
76.12
70.21
77.96-:aa
76.35
82.27 =.
Enron
85.8621m:
62.08
61.40..m
62.90
60.724e.
67.11
72.37
62
80.47
67.07-1
74.60-:
Social Evo.
88.01a 88.7221 in 93.97=x
90.652
e
79.832
94. 10
94.01a
84.892 o 96.7621 i
16
96 36.38
AP
UCT
63.16 s2.47
30
70.73
64.54
76.65.2mm
$1.64a
51.58
85.50
12.13-1.
78.50=:
Flights
61.012
62.8321 a 64.72
64.72-...
50.32g
in
56.82
64 14.5021
65.2992
51.00gg
53-40
57.11 m
54. 64.6322 m
Can. Par.,
52.58 52,24
56.46...e
54.1810w
67.061...
16
55.7610.6
61.71is.>
50.66a...
87.22...
87
US Legis.
52.94.2a: 62.10
51.83
2.a3 61.18
55.56
53.87
52.03
64.61
is.2
58.37
56.31 2.3
66.95
UN Trade
a5.43 55
55.58_a.x
52.80
54.97
55.66
54.88
60.96.2
52.50
78.95
UN Vote
61.17...a
60.29 m.
53.08
a.s
63.71
18.01
11.3-
18. 18.10
64.8
65.70
52.61
65.53
Contact
a0.43
89.22
94.14
12g
74.19
90.40
84.13
90.68
90.55
93.57
Avg. Rank
7.38
7.77
5,54
6.23
8.08
5.92
5.23
7.62
4,23
4.77
3.15
Wikipedia 61. 87 67.042 v
78.38 a 76.76gn
02.022..4
79.79
82.882
40.9024 v
73.30
68.30 m
67.96 67.96
Reddit
61 11..9 60.4
61.39....
61.55
61.91.ua
61.
16..
61.27
58.31 to.s
61.02....
61.80
MOOC
61.22
71.07 a...
77.68
T1.69
69.53
72.52
68.00....
75.98
80.77
84.46
LasiEM
68
66.99
....
70.07
61.88..
72.02
70.73
27.10
Enton
65.32 61.50
07.83-2..
62 02.68....
62.27
61.06
68.19
61.69....
78.90
65.79
74 50 .0
Social Evo.
88.50
87.93an on 91.85 31.88_..7
92, 10
63.54gnax
83.62
84,80
96
96.91gmm
76
AUC
U:C
80.272-
51.282g
62. 2922
62.00ga
50.30ge
70.42g
70.97
42.08kn
81.36ga
66 18.58
71. 21.3721
Flights
60.72
61.99
50.66
56.58
63.49_mm
63.32gm
48.36g3
49.74
56.05
50.05
Can. Parl,
51.61ge 52.33gn
58.15
05.432m
6000
56. a1
56.63g
61.83
48.9322
88.51g0m
68 98
US Legis.
58 12..2 67.94
19.90
19.99.....
G4.87
54.iaaa.
52.12....
19.28
66.9614.>
62.82
56.07=x.e
68.37
UN Trade
58.71 v7.
59.98
35.62
60.88
61.01
59.71
70.31
62.54
57.28
80.78
UN Vote
85.29
64.
io 51. 51.78.4.4
68.58
48.044
54.85
45.57
67.61.1.
69.44gam
50.87-2m
65.85
Contact
80.80
88.87
93.76
88.85
71.79
90.37-
90.0
8471
92:00)
94.14
93.47
Avg. Rank
7,23
8.00
5.85
6.00
7.46
6.00
5.46
7.92
4.31
4.46
3.31
24

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction list the limitations of existing relative encodings, and the goal of this paper is to tackle such limitations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitation in the appendix.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
25

---

Justification:
All theorems include the full sets of assumptions and proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide the implementation details of method in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
26

---

Answer: [Yes]
Justification:
We include our codes in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /niiss wwtppcccpppppaeeeccccecccccceeee / siiissssiiiiiyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Implementation details are shown in the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, the appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report the mean and standard deviation in tables that record the experimen- tal results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
27

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We list the compute resources of our experiments in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:://earrsp..ccpplll httpehhhhhhucceeeeeeeeee....eeee
Answer: [Yes]
Justification: Our paper follows the NeurlPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss the potential societal impacts in the appendix.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
28

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification:
The proposed method does not have high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We follow the license of each asset and cite them properly.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
29

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification:
We do not provide new assets this paper.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not include crowdsourcing experiments and research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not include crowdsourcing experiments and research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "jejAspNdmG", "reviewer": "Reviewer_vApy", "summary": "The article investigates the application of relative encodings in the task of link prediction over temporal networks. Initially, the authors formally unify previously used relative encodings, such as DyGFormer, PINT, NAT, and CAWN, within a unique framework. Subsequently, they propose a novel model, TPNet, and conduct comparative evaluations using several datasets and competitors.", "questions": "If I understand correctly, the authors introduce a weight decay mechanism to exponentially decrease the weight of older interactions. While this decision is well-motivated by previous studies, it is well known that the recurrence of interactions is fundamentally important in social networks (e.g., sociopatterns.org). I am curious whether the temporal periodicity of interactions is maintained with this approach. Could the authors discuss this aspect in more detail?", "limitations": "The authors discussed the limitations of the model in the appendix.", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The provided framework offers a clearer and broader perspective on existing approaches based on temporal walks. The source code is well-commented and likely to be highly usable. The experimental setup investigates various competitors, datasets, and negative sampling techniques.", "weaknesses": "A fundamental concept in the article is \"relative encoding.\" However, the intuition behind this concept is not introduced until line 119. I recommend presenting the meaning of \"relative encoding\" earlier in the article for better clarity and understanding.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comments. In response, we have discussed the temporal periodicity modeling ability of our score function and moved the motivation of the relative encoding earlier according to your suggestion. We hope this addresses your concerns and are happy to answer any further questions you may have.\n\n\n**Q1. If I understand correctly, the authors introduce a weight decay mechanism to exponentially decrease the weight of older interactions. While this decision is well-motivated by previous studies, it is well known that the recurrence of interactions is fundamentally important in social networks (e.g., sociopatterns.org). I am curious whether the temporal periodicity of interactions is maintained with this approach. Could the authors discuss this aspect in more detail? .**\n\nAlthough the time decay score function (defined in line 187 of the paper) is not specifically designed for modeling temporal periodicity, it can still capture periodic patterns to some extent. To illustrate this, consider a simple example where two nodes, $u$ and $v$, interact once every $\\Delta t$ time interval.  Then, we can divide the time into equal-size durations $(0,\\Delta t),(\\Delta t,2\\Delta t),...$, and examine how the element of the temporal walk matrices changes within each duration.  Specifically, assuming the current time $t \\in (n \\Delta t, (n+1)\\Delta t)$ with $n>0$, the timestamps of the historical interactions between $u$ and $v$ will be $[\\Delta t, 2\\Delta t,..., n\\Delta t]$,  and the element of the one-step temporal walk matrix $A_{u,v}^{(1)}(t)$ will be $A_{u,v}^{(1)}(t) = \\sum_{k=1}^n\\exp(-\\lambda (t-k\\Delta t))$ (i.e., sum the scores of historical interactions). Since $\\lambda >0$, $A_{u,v}^{(1)}(t)$ will decrease as $t$ increases within $(n\\Delta t, (n+1)\\Delta t)$ and the value of $A_{u,v}^{(1)}(t)$ is within $(\\sum_{k=1}^n \\exp(-\\lambda k \\Delta t),\\sum_{k=0}^{n-1}\\exp(-\\lambda k \\Delta t))$ (by setting $t$ to  $(n+1)\\Delta t$ and $n\\Delta t$ respectively). The maximum value $\\sum_{k=0}^{n-1}\\exp(-\\lambda k \\Delta t)$ is at least 1 since $\\exp(-\\lambda 0\\Delta t) =1$ and all other terms are nonnegative. For the minimum value $\\sum_{k=1}^n \\exp(-\\lambda k \\Delta t)$,  if $\\lambda$ is large enough, it will be less than 1. For example, if $\\exp(-\\lambda  \\Delta t) < \\frac{1}{4}$, we have $\\sum_{k=1}^n \\exp(-\\lambda k \\Delta t) < \\sum_{k=1}^n \\frac{1}{4^k} < \\frac{1}{2}$. Based on the above analysis, $A_{u,v}^{(1)}(t)$ exhibits the following behavior over time: going up to a value that is no less than 1 at the beginning of each duration and then decreasing to a value that is lower than 1 at the end of each duration, which acts like a periodic function.  Then we can infer that $u$ and $v$ are likely to interact when $A_{u,v}^{(1)}(t)$ is low and unlikely to interact when $A_{u,v}^{(1)}(t)$ is high, capturing this periodic evolution pattern.  We show a visual illustration in Figure 1 of the attached PDF file for better understanding. \n\n\n\n**W1. A fundamental concept in the article is \"relative encoding.\" However, the intuition behind this concept is not introduced until line 119. I recommend presenting the meaning of \"relative encoding\" earlier in the article for better clarity and understanding.**\n\nWe have added the motivation for relative encoding to the second section of the Introduction and improved the explanation of Figure 1 for better clarity and understanding. The revised part of the second section is as follows (changes highlighted in bold):\n\n>  Relative encodings have become an indispensable module for effective temporal link prediction [6-9] where, without them, node representations computed independently by neighbor aggregation will fail to capture the pairwise information. As the toy example shown in Figure 1, A and F will have the same node representation due to sharing the same local structure. Thus it can not be determined whether D will interact with A or F at $t_3$ according to their representations. **However, by assigning nodes relative encodings (i.e., additional node features, detailed in Section 2.2) specific to the target link before computing the node representation, we can highlight the importance of each node and guide the representation learning process to extract pairwise information specific to the predicted link from the subgraph**. For example, in Figure 1, we can infer from the relative encoding of E **(in red circle)** that D is more likely to interact with F than with A since D and F share a common neighbor, E.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5AGG4uxFZQ", "reviewer": "Reviewer_SMMz", "summary": "Based on the analysis of traditional methods, this paper proposes a unified framework for relative encoding and introduces a new temporal neural network, TPNet. This model not only addresses the high time complexity issues of traditional methods but also enhances relative encoding by incorporating factors such as time decay effects.", "questions": "please see weaknesses", "limitations": "n/a", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1、The authors propose a unified framework for relative encoding, treating them as a function of temporal random walk matrices.\n\n2、The temporal random walk matrix not only takes into account temporal and structural information but also incorporates the effects of time decay.\n\n3、To reduce computational complexity, the authors proposed an approximation scheme for the temporal random walk matrix, detailed in Algorithm 1.\n\n4、The authors conducted thorough axiomatic proofs, providing solid theoretical support for the effectiveness of the TPNet network", "weaknesses": "1、If the authors could provide a comparison of memory usage, it would make the model more convincing.\n\n2、This paper does not provide an analysis of the impact of different functions g on relative encoding.\n\n3、The author did not compare with the latest models (published in AAAI 2024 or WWW 2024) in Table 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your helpful reviews. In response, we have reported the memory usage of different methods, discussed the construction of our decoding function $g(\\cdot)$, and compared TPNet with a new temporal link prediction method. We hope this addresses your concerns and are happy to answer any further questions you may have.\n\n**W1. If the authors could provide a comparison of memory usage, it would make the model more convincing.**\n\nWe report the peak GPU memory usage in the following table, measured in MB. The last line of the table reports the relative memory usage,  calculated by dividing each method's memory usage by TCL's (i.e., method with the smallest average memory usage) and then averaging across datasets. \n\n|Dataset|TCL|JODIE|DyRep|TGN|TPNet (ours)|NAT|TGAT|GraphMixer|DyGFormer|CAWN|PINT|\n|:-----:|:-:|:---:|:---:|:-:|:---------:|:-:|:-:|:--------:|:-------:|:-:|:-:|\n|Wikipedia|171|247|253|271|299|430|570|714|279|633|2278|\n|Reddit|510|838|839|898|663|1265|909|1049|645|972|3381|\n|MOOC|336|446|459|464|470|835|735|877|673|1279|1405|\n|LastFM|911|1022|1038|1039|1044|1960|1309|1450|1643|2818|1113|\n|Enron|145|113|136|138|254|361|542|684|483|606|862|\n|Social Evo.|1439|1406|1430|1431|1504|2938|1838|1980|1547|2382|2154|\n|UCI|102|90|111|111|205|224|502|643|210|1045|890|\n|Flights|1335|2190|2192|2259|1503|2989|1733|1875|1673|2277|5532|\n|Can. Parl.|110|63|85|86|211|239|509|651|3150|2017|818|\n|US Legis.|101|62|85|86|201|297|500|642|440|563|810|\n|UN Trade|394|376|399|400|514|811|793|935|733|1337|1124|\n|UN Vote|741|735|759|760|870|1592|1140|1282|926|1684|774|\n|Contact|1653|1791|1813|1814|1794|3428|2052|2195|1761|2596|2544|\n|Rel. Memory|1.00|1.08|1.16|1.18|1.46|2.31|2.64|3.23|3.97|4.73|5.12|\n\nAs shown in the above table, TPNet has lower relative memory usage than other link-wise methods (i.e., DyGFormer, NAT, CWAN, and PINT), showing its efficient memory usage. Additionally, on average, TPNet’s memory usage is 1.46 times that of the most memory-efficient method (i.e., TCL). Considering TPNet's SOTA performance and superior computational efficiency, this level of memory usage is satisfactory. \n\n**W2. This paper does not provide an analysis of the impact of different functions g on relative encoding.**\n\nThe function $g(\\cdot)$ introduced in Equation (3) can be considered a decoding function that extracts pairwise information from the constructed temporal walk matrices.  Unlike existing methods that use predefined $g(\\cdot)$, we design it as a learnable function. Specifically, we feed the raw pairwise feature into an MLP ( line 265 of the paper), which serves as our decoding function $g(\\cdot)$. By optimizing the learnable parameters in the MLP, we can adaptively determine the most suitable function $g(\\cdot)$ for different graphs, better modeling graph dynamics.\n\n**W3. The author did not compare with the latest models (published in AAAI 2024 or WWW 2024) in Table 1**\n\nAfter reviewing the papers published in AAAI 2024 and WWW 2024, we did not find any that were closely related to our work. However, we found an ICLR 2024 paper that proposes a new temporal link prediction model called FreeDyG [1], which adopts a Fourier Transformer to enhance the node representation learning process. We report AP under random negative sampling for performance comparison. \n\n|                      |         |    Wikipedia     |      Reddit      |       MOOC       |      LastFM      |      Enron       |   Social Evo.    |       UCI        |\n| -------------------- | ------- | :--------------: | :--------------: | :--------------: | :--------------: | :--------------: | :--------------: | :--------------: |\n| Transductive Setting | FreeDyG |   99.26 ± 0.01   | **99.48 ± 0.01** |   89.61 ± 0.19   |   92.15 ± 0.16   |   92.51 ± 0.05   | **94.91 ± 0.01** |   96.28 ± 0.11   |\n|                      | TPNet   | **99.32 ± 0.03** |   99.27 ± 0.00   | **96.39 ± 0.09** | **94.50 ± 0.08** | **92.90 ± 0.17** |   94.73 ± 0.02   | **97.35 ± 0.04** |\n| Inductive Setting    | FreeDyG | **98.97 ± 0.01** | **98.91 ± 0.01** |   87.75 ± 0.62   |   94.89 ± 0.01   |   89.69 ± 0.17   | **94.76 ± 0.05** |   94.85 ± 0.10   |\n|                      | TPNet   |   98.91 ± 0.01   |   98.86 ± 0.01   | **95.07 ± 0.26** | **95.36 ± 0.11** | **90.34 ± 0.28** |   93.24 ± 0.07   | **95.74 ± 0.05** |\n\nAs shown in the above table, TPNet significantly outperforms FreeDyG on MOOC, LastFM, and UCI, while exhibiting similar performance on other datasets, demonstrating its superiority.  We also report the inference time (s/epoch) to compare efficiency.\n\n|         |  Wikipedia   |    Reddit     |     MOOC      |    LastFM     |     Enron     |  Social Evo.  | UCI           |\n| :-----: | :----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | ------------- |\n| FreeDyG |    12.37     |     61.11     |     32.19     |    102.73     |     9.75      |    163.94     | 4.75          |\n|  TPNet  |     2.51     |     11.10     |     6.38      |     22.71     |     1.95      |     33.34     | 0.93          |\n| Speedup | 4.93$\\times$ | 5.51 $\\times$ | 5.05 $\\times$ | 4.52 $\\times$ | 5.00 $\\times$ | 4.92 $\\times$ | 5.11 $\\times$ |\n\nAs shown in the above table, TPNet is more computationally efficient than FreeDyG, achieving at least a 4.52 $\\times$ speedup.\n\n[1] Tian, Yuxing, Yiyan Qi, and Fan Guo. \"FreeDyG: Frequency Enhanced Continuous-Time Dynamic Graph Model for Link Prediction.\" *The Twelfth International Conference on Learning Representations*. 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nLJBdGOiK1", "reviewer": "Reviewer_YNEN", "summary": "The paper introduces a framework for analysis of relative encodings as a function of random walk matrices, and a new model for temporal link prediction. The new model offers SOTA performance on multiple link prediction datasets, and achieves this performance more efficiently than current best models. The design is of the model is explained in detail.", "questions": "1. Line 265: Why does ReLU reduce estimation error? Is this an empirical result, or an architectural consideration specific to your data? Please clarify.\n\n2. Line 43: The second argument sounds a bit vague. Could specific examples be mentioned for methods that use and don't use temporal information in constructing their embeddings?\n\n3. Minor point on code: distutils has been removed in python 3.12 and above. To run the code I've had to install the following dependencies in addition to the ones listed: setuptools, numba, sklearn. I've had to fix the following issue.\n\n```{python}\nset(random.sample(test_node_set, int(0.1 * num_total_unique_node_ids)))\n```\nHad to be changed to:\n```{python}\nset(random.sample(sorted(test_node_set), int(0.1 * num_total_unique_node_ids)))\n```\n\t\t\nThis happened installing your code in a new python 3.12 environment.", "limitations": "The limitations are briefly discussed in the appendix.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is an overall good paper which proposes and evaluates a new SOTA approach for temporal link prediction. It also introduces an original framework for unifying a range of existing methods.\n\n1. The provided code is sufficiently commented, and detailed instructions for setup are provided, along with utility functions to start the training process.\n2. Extensive evaluation has been done of the proposed model, and SOTA performance across a range of datasets has been demonstrated.\n3. Current methods have been posed in the newly proposed framework, which is an interesting analytical contribution.\n\nClearly presented and significant contribution to the field of temporal link prediction.", "weaknesses": "1. The limitations of the approach are only briefly discussed in the appendix.\n2. Although the code is well presented, it did not run out of the box for me. Some effort was required to install additional dependencies not listed in the requirements.txt, and to fix a runtime error in the sampling algorithm of the DataLoader.\n\nMinor points / text linting suggestions:\n\nLine 81: What is a \"unified formation\", did you mean \"formulation\"?\n\nLine 94: Style \"all the interactions happen\" -> \"all the interactions that happen\"\n\nLine 128: Doesn't A^(i) aggregate the i-step temporal walks, instead of k-step? Typo?\n\nLine 187: \"The value of score function..\" -> \"The value of the score function\".\n\nLine 202: What is d? The node degree or dimensionality? Please define. Also in line 2, Algorithm 1.\n\nLine 203: Typo enumerating the H vectors. The index 1 is repeated, whereas it should be followed by 2.\n\nLine 205: Style \"Pseudocode code\" -> \"Pseudocode\"\n\nLine 211: Having the integer \"i\" in the exponent of e could be misleading for a reader who is skimming to get an overview of the paper. This letter is usually reserved as the imaginary unit when exponentiating e, so ideally pick another letter as the index.\n\nLine 261: \"and obtained\" -> \"and obtain\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments. In response, we have clarified how ReLU can reduce estimation error and discussed the utilization of temporal information in existing methods. We have also revised the paper and code according to your suggestions. We hope this addresses your concerns and are happy to answer any further questions you may have.\n\n**Q1 Line 265: Why does ReLU reduce estimation error? Is this an empirical result, or an architectural consideration specific to your data? Please clarify.** \n\nIt is an architectural consideration specific to our construction of temporal walk matrices. Recall that our score function $s(\\\\cdot)$ for a temporal walk $W=[(w\\_0,t\\_0),(w\\_1,t\\_1),\\\\cdots,(w\\_k,t\\_k)]$ is $s(W)=\\\\prod\\_{i=1}^k e^{-\\lambda(t-t\\_i)}$, which is always larger than zero.  Therefore, each element of the corresponding temporal walks matrices $A\\_{u,v}^{(k)}(t) = \\\\sum\\_{W \\\\in \\\\mathcal{M}\\_{u,~v}^k} s(W)$ should be non-negative. From theorem 2, we know that the inner product of the node representations is approximately equal to the inner product of rows from temporal walk matrices, which is $\\\\langle \\\\bar{\\\\boldsymbol H}\\_u^{(i)}(t), \\\\bar{\\\\boldsymbol H}\\_v^{(j)}(t) \\\\rangle \\\\approx \\\\langle \\\\boldsymbol A\\_u^{(i)}(t),\\\\boldsymbol A\\_v^{(j)}(t) \\\\rangle$ (appears in line 225).  In line 265, each element of the raw pairwise feature $ \\\\tilde{\\\\boldsymbol f}\\_{u ,v}$ is the inner product of node representations from $u$ and $v$ , which can be considered as an estimation of the inner product between the u-th and v-th rows of the temporal walk matrices. Since each element of temporal walk matrices is non-negative, the inner product of two rows from temporal matrices should also be non-negative. Thus we feed the raw pairwise feature into RELU to reduce estimation error.  Specifically, consider the l-th element of raw pairwise feature $ \\\\tilde f\\_{u,v}[l]$ and assume it is the inner product of $\\\\bar{\\\\boldsymbol H}\\_u^{(i)}(t)$ and $\\\\bar{\\\\boldsymbol H}\\_v^{(j)}(t)$, which can be considered as an estimation of the inner product of $\\\\boldsymbol A\\_u^{(i)}(t)$ and $\\\\boldsymbol A\\_v^{(j)}(t)$. Then if $\\\\tilde f\\_{u,v}[l]$ < 0,  using $|\\\\cdot|$ to denote the absolute vlaue , we will have $\\\\left |\\\\langle \\\\boldsymbol A\\_u^{(i)}(t),\\\\boldsymbol A\\_v^{(j)}(t) \\\\rangle - \\\\tilde f\\_{u,v}[l]\\\\right| >\\\\left |\\\\langle \\\\boldsymbol A\\_u^{(i)}(t),\\\\boldsymbol A\\_v^{(j)}(t) \\\\rangle - 0\\\\right |$ since $\\\\langle \\\\boldsymbol A\\_u^{(i)}(t),\\\\boldsymbol A\\_v^{(j)}(t) \\\\rangle \\\\geq 0$ . Therefore, setting the negative value to zero by feeding $\\\\tilde{\\\\boldsymbol f}\\_{u ,v}$ into RELU will have a lower estimation error than using the original value.\n\n**Q2 Line 43: The second argument sounds a bit vague. Could specific examples be mentioned for methods that use and don't use temporal information in constructing their embeddings?**\n\nSure. We list the score function $s(\\cdot)$ of methods that are analyzed in Section 2.2.2 in the following table, where $W=[(w_0,t_0),..,(w_k,t_k)]$ indicates a temporal walk and $Z_i= \\\\sum\\_{\\\\{(w',w),t'\\\\} \\\\in \\\\mathcal E\\_{w\\_{~i},~~t\\_i}} \\\\exp(-\\alpha (t\\_i-t'))$ indicates the normalize term of CAWN.\n\n| DyGFormer | PINT     | NAT      | CAWN                                                         |\n| --------- | -------- | -------- | ------------------------------------------------------------ |\n| $s(W)=1$  | $s(W)=1$ | $s(W)=1$ | $s(W)=\\\\prod\\_{i=0}^{k-1}\\\\frac{\\\\exp(-\\alpha(t\\_i-t\\_{i+1}))}{Z_i}$ |\n\n\nAs shown in the above table, only CAWN considers the temporal information carried by a temporal walk. The score functions of the other three methods always yield one, so the element of their temporal walk matrices merely counts the number of temporal walks, ignoring the temporal information. For more discussion about existing methods, please refer to the conclusion starting from line 163 of the paper.\n\n**Q3 & W2: Although the code is well presented, it did not run out of the box for me. Some effort was required to install additional dependencies not listed in the requirements.txt, and to fix a runtime error in the sampling algorithm of the DataLoader.**\n\nSorry for the incomplete information regarding the required environment.  The Python version used in our experiments is Python 3.9. We will add this information to the `requirements.txt` file and review our dependencies to ensure that no necessary packages have been omitted. Thanks for your efforts to adapt our code to the latest environment and we will revise our code according to your suggestion.\n\n**W1 The limitations of the approach are only briefly discussed in the appendix.**\n\nWe will move the limitation section into the main body of our paper and expand the discussion.\n\n**W3 Minor points / text linting suggestions**\n\nWe have revised the paper according to your suggestions for lines 81, 94, 187, 203, 205, 211, and 261.\n\nFor line 128: Yes, it is a typo, and we will correct it.\n\nFor line 202: $d$ indicates the dimensionality, and we will replace it with $d_R$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all reviewers for their time and valuable comments. We are pleased that the reviewers acknowledge the value of our work in providing a cohesive perspective on existing methods (Reviewers vApy, SMMz, YNEN), proposing a novel method (Reviewer vApy) with solid theoretical support (Reviewer SMMz), and conducting extensive experiments to verify the effectiveness and efficiency of the proposed method (Reviewers vApy, YNEN).

To the best of our efforts, we have provided thorough responses to address the issues raised by each reviewer, which mainly consist of:

- Clarification on method design and analysis of existing methods
  - Discussion on the temporal periodicity modeling capability of the score function.
  - Discussion on the construction of the function $g(\cdot)$.
  - Clarification of why ReLU can reduce estimation error.
  - Clarification on the use of temporal information in constructing temporal walk matrices.
- Additional experimental results
  - Reporting memory usage of different methods.
  - Comparison with a new temporal link prediction method.
- Reorganization of the paper.
  - Move the motivation of the relative encoding earlier.
  - Move the limitation section to the main body of the paper.

Meta-review: The study explores the use of relative encodings for temporal link prediction. It first provides a unified view of relative encoding as a function of temporal walk matrices. Then it incorporates a time decay effect on this matrix, named TPNet. Finally, authors provide both theoretical and empirical analysis to demonstrate the effectiveness of the proposed approach. 

All the reviewers are quite positive about this submission. Concerns raised by reviewers were addressed properly. 

To sum up, it is a solid paper. I’d like to recommend its acceptance.
Decision: Accept (poster)