Improving Temporal Link Prediction via Temporal Walk Matrix Projection

Authors: xiaodong  lu
leilei  sun
tongyu  zhu
weifeng  lv
Venue: NeurIPS_cc_2024_Conference
Published: 2024-04-30 16:38:17

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.

Main paper: 
 intorduction: 
 Many real-world dynamic systems can be abstracted as a 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 a 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 a series of real-world tasks such as 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] [7] [8] [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 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 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 (detailed discussed in Section 2.2). Although achieving remarkable success, injecting pairwise information based on relative encodings is still far from satisfactory. (For each link (u, v, t), the relative encoding here for a node w is [g(u, w), g(v, w)],where g(u, w) = 1 if there is an interaction between u and w before t, otherwise g(u, w) = 0.) 1) On Concept, existing ways of constructing relative encodings are fragmented as they are derived from different heuristics. There still lacks a unified view on the connections between different 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 information is ignored. 3) On Computation, existing methods for relative encodings are inefficient, 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 computational bottleneck for some methods (shown in Section 4.2).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 to 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) A Effective and Efficient Method (Method Design and Computation). Based on our analysis, we propose a Time decay matrix Projection-based graph neural Network for temporal link prediction, named TPNet for short. TPNet introduces a 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 a series of node representations by random feature propagation, which can be efficiently updated when the graph structure changes and is storage-efficient. Importantly, such node representations can be shared by different link likelihood computation processes to 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. 
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.Definition 1 (Temporal Graph). A temporal graph can be considered as a sequence of non-decreasing chronological interactions G = [({u 1 , v 1 }, t 1 ) , ({u 2 , v 2 }, t 2 ) , • • • ] with 0 ≤ t 1 ≤ t 2 ≤ • • • , where ({u i , v i }, t i ) can be considered as a undirected link between u i and v i with timestamp t i . Each node u can be associated with node feature x u ∈ R d N , and each interaction ({u, v}, t) has link feature e t u,v ∈ R d E , where d N and d E 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 t (i.e., {({u ′ , v ′ }, t ′ )|t ′ < t}) and two nodes u, v, the temporal link prediction task aims to predict whether there will be an interaction between u and v at t. Definition 3 (K-hop Subgraph). We use the notation G(t) = (V(t), E(t)) to denote the graph snapshot at t, where E(t) includes all the interactions that happen before t and V(t) includes all the nodes appear in E(t). Besides, we defined the k-hop subgraph of node u as G k u (t) = (V k u (t), E k u (t), where V k u (t) ⊂ N (t) is the set of nodes whose shortest path distance to u is less than k on G(t) and E k u (t) ⊂ E(t) is the set of interactions between V k u (t). Definition 4 (Temporal Walk). A k-step temporal walk W on G(t) is a sequence of node-time pair with decreased temporal order [6] , which can be denoted as W = [(w 0 , t 0 ), • • • , (w k , t k )] with t = t 0 > t 1 > • • • > t k and ({w i , w i+1 }, t i+1 ) is an edge on G(t) for 0 ≤ i ≤ k -1. Figure 2 shows a visual illustration of a temporal walk. Here, we stipulate the first timestamp t 0 as the current time t to avoid undefinedness of t 0 . We use the notation M k u,v (t) to denote the set of all k-step temporal walks from u to v on G(t). Specially, M 0 u,w (t) = {[(u, t)]} if u = w and M 0 u,w (t) = ∅ otherwise. When there is no ambiguity, we replace M k u,v (t) with M k u,v .Given a future link (u, v, t) to be predicted, existing temporal link prediction methods (referred as node-wise methods) usually first learn the node representations h u (t) and h v (t) independently, which are obtained by encoding their k-hop subgraphs,EQUATIONwhere X N u,k and X E u,k are the features of nodes and edges in G k u (t) respectively2 . The f enc (•) 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 p t u,v is givenp t u,v = f dec (h u (t), h v (t)). The f dec (•) is a decoding function that maps the node representations into link likelihood such as an MLP with a 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 r w| (u,v) for each node w ∈ V k u (t) ∪ V k v (t) as an additional node feature (Detailed construction way for different methods will be introduced in Section 2.2.2). Then Equation (1) will be changed intoEQUATIONwhere X R u,k is the relative encodings for nodes in G k u (t) and X N u,k ⊕ X R u,k indicate the new node features obtained by concatenating X N u,k and X R u,k . Intuitively, the relative encoding r w|(u,v) 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 w| (u,v) is the concatenation of two similarity features r w|u and r w|v , where r w|u /r w|v encodes some form of similarity between u/v and w (e.g., the number of k-step temporal walks from u to w). Although the designs of similarity feature r w|u for different methods are induced from different heuristics, we find that they can be unified in a function about the temporal walk matrix, which isr w|u = g([A (0) u,w (t), A (1) u,w (t), • • • , A (k) u,w (t)]), A (i) u,w (t) = W ∈M i u,w s(W ) for 0 ≤ i ≤ k. (3)The s(•) here is a score function that maps a temporal walk to a scalar and A (i) (t) denotes an i-hop temporal walk matrix whose each entryA (i)u,w is the sum of the score of all i-step temporal walks from u to w. g(•) is a function applied on the vector of [A(0) u,w (t), A (1) u,w (t), • • • , A (k)u,w (t)] ∈ R k+1 to extract 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 existing relative encodings and show how they can be represented in the form of Equation (3).Our analysis focuses on the four representative link-wise methods DyGFormer, PINT, NAT, and CAW, which cover all the link-wise methods in the benchmark of dynamic link prediction [9] .DyGFormer [9] . The r w|u of DyGFormer is a 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., s(W ) = 1 in for any W ), which will make A (k) u,w 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.e., g([x 0 , x 1 , .., x k ]) = x 1 ) will make Equation (3) generate the similarity feature of DyGFormer.PINT [8] . The r w|u of PINT is a (k + 1)-dimensional vector, where r w|u i is the number of (i -1)-step temporal walks from u to w for 1 ≤ i ≤ k + 1. Setting s(•) and g(•) can be set to a one-const function and an identity function respectively will make Equation (3) outputs the similarity feature of PINT.NAT [7] . NAT maintains a series of fix-sized hash maps sEQUATIONu and generates the r w|u based on the hash maps. As proved in Appendix A.1, if the size of the hash maps becomes infinite, the r w|u is equivalent to a (k + 1)-dimensional vector, where, for 1 ≤ i ≤ k + 1, r w|u i = 1 if the shortest temporal walk from u to w is less than i; otherwise, r w|u i = 0. Let h(•) be a binary function where h(x) = 1 if x > 0 and h(x) = 0 otherwise. Setting the s(•) to be a one-const function and g(•) to a function of g([x 0 , x 1 , ...,x k ]) = [h( 0 i=0 x i ), h( 1 i=0 x i ), ..., h( k i=0 x i )]can make the Equation (3) generate the similarity feature of NAT.CAWN [6] . The similarity feature r w|u of CAWN reflects the probability of a node w being visited when performing a temporal walk from u. Specifically, CAWN first samples a set of temporal walks beginning from u based on a causal sampling strategy. Then, for each node w, the similarity feature r w|u is extracted based on its occurrence in the sampled walks. As proved in Appendix A.2, the similarity feature r w|u is the estimation of a (k + 1)-dimensional vector, where, for1 ≤ i ≤ k + 1, r w|u iis the probability of visiting w through a (i-1)-step temporal walk matrix based on the sampling strategy of CAWN, which can be represented as rw|u i = W ∈M i-1 u,w s ′ (W ). The value s ′ (W ) for a given tem- poral walk W = [(w 0 , t 0 ), (w 1 , t 1 ), ..., (w k , t k )] is defined as k-1 i=0 exp(-α(ti-ti+1)) ({w ′ ,w},t ′ )∈E w i ,t i exp(-α(ti-t ′ )), where α is hyperparameter to control the sampling process, E wi,ti = {({w ′ , w}, t ′ )|t ′ < t i } is the set of interactions attached to w i before t i , and exp(-α(ti-ti+1))({w ′ ,w},t ′ )∈E w i ,t i can be considered as the probability of moving from (w i , t i ) to (w i+1 , t i+1 ) 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.According to the above analysis, we can conclude that (i) Equation (3) provides a 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,λ,k,n,d R ) Initialize H (0) , H (1) , ..., H (k) ∈ R n×d R as zero matrix ; Fill H (0) with entries independently drawn from N (0,1 d R ) ; for (u, v, t) ∈ G do for l = k to 1 do H (l) u = H (l) u + e λt * H (l-1) v ; H (l) v = H (l) v + e λt * H (l-1) u ;Return H (0) , H (1) , .., H (k) ; walks, which needs time-consuming graph sampling and may introduce large estimation errors. In the next section, we will present a new temporal walk matrix to simultaneously consider the temporal and structural information and show how to efficiently maintain the proposed temporal walk matrix. 
methodology: 
 TPNet mainly consists of two modules: Node Representation Maintaining (NRM) and Link Likelihood 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 a 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.Temporal Matrix Construction. Based on the Equation (3), designing a temporal walk matrix relies on the definition of the score function s(•), where the element of a temporal walk matrix isA (k) u,v (t) = W ∈M k u,v s(W ).Unlike most previous methods that only count the number of temporal walks, we consider the temporal information carried by a temporal walk in s(•) to simultaneously consider the temporal and structural information. Formally, let t be the current time, given a temporal walk W = [(w 0 , t 0 ), (w 1 , t 1 ), .., (w k , t k )], the value of the score function is s(W ) = k i=1 e -λ(t-ti) , where λ > 0 is a hyperparameter to control the time decay weight. As the current time t goes on, for each interaction ({w i , w i+1 }, t i+1 ) in the temporal walk W , its weight e -λ(t-ti) 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 as time goes on, benefiting better modeling the graph evolution patterns. In the following part of Section 3, the notation of s(•) and A (k) (t) will specifically refer to the score function and temporal walk matrix proposed in this part. Besides, for A (0) (t), we stipulate it as an identity matrix constantly.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 × n) space complexity to store. Thus, we implicitly maintain the temporal walk matrices by maintaining a series of node representationsH (0) (t), H (1) (t), ..., H (k) (t) ∈ R n×d R , where d R ≪ n is the dimension of node representations and H (l) u (t) ∈ R d Rencodes the information about the l-step temporal walks beginning from u for 0 ≤ l ≤ k. The node representations will be updated when a new interaction occurs. Specifically, we first construct a random feature matrix P ∈ R n×d R , where each entry of P is independently drawn from Gaussian distribution with mean 0 and variance 1 d R . Then we initialize H (0) (t) as P and H (1) (t), H (2) (t), ..., H (k) (t) as zero matrix. When a new interaction (u, v, t) occurs, for 1 ≤ l ≤ k, we update the representations of u and v byEQUATIONwhere the t + denotes the time right after t. A pseudocode for maintaining the node representations is 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 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 graph G have different timestamps, the obtained representations H (0) (t), H (1) (t), ..., H (k) (t) satisfy e -λlt * H (l) (t) = A (l) (t)P for 0 ≤ l ≤ 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.1. The above theorem shows that the obtained node representation is 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 ϵ ∈ (0, 1), let ∥ • ∥ 2 denote the L2 norm, c l1,l2 u,v denote 1 2 (∥A(l1) u (t)∥ 2 2 + ∥A (l2) v (t)∥ 22 ), andH(l) (t) denote e -λlt * H (l) (t), if dimension d R of node representations satisfy d R ≥ 24ϵ 2 log(4 1/3 (k + 1)n), then for any 1 ≤ u, v ≤ n, and 0 ≤ l 1 , l 2 ≤ k, we haveEQUATIONwhere ⟨•, •⟩ denotes the inner product and | • | denotes taking 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., ⟨ H(l1)EQUATIONv (t)⟩). Specifically, given any error rate ϵ, if the dimension of the node representations satisfies a certain condition, the difference between ⟨ H(l1)EQUATIONv (t)⟩ for any u, v, l 1 , l 2 will be less than ϵc l1,l2 u,v with high probability (≥ 1 -1 (k+1)n ). The error rate can approach 0 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 d R . 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 A (0) (t) being the one-hot encoding of i (since it is an identity matrix), we have ⟨A (0) u (t), H(0) w (t)⟩, • • • , ⟨ H(k) u (t), H(0) w (t)⟩].Remark. Compared to directly computing the temporal walk matrices A (0) (t), .., A (k) (t), which needs to enumerate the temporal walks and O((k + 1)n 2 ) space complexity to store, maintaining the node representations largely improve the computation and storage efficiency, which only needs O((k+ 1)nd R ) space complexity to store and O(kd R ) time complexity to update when a new interaction occurs. Actually, Theorem 2 is the direct result of Theorem 1 based on Johnson-Lindenstrauss 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 a 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 it. 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.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 a pairwise feature f u,v (t) from the node representations obtained in Section 3.1. Then we compute the node embeddings h u (t) and h v (t) for node u and v respectively based on their historical interactions. Finally, we give the link likelihood based on h u (t), h v (t), f u,v (t). For notation simplicity, we omit the suffix of h u (t), h v (t), f u,v (t) and denote them as h u , h v , f u,v in the following part.Pairwise Feature Decoding. Although we can obtain the (k + 1)-dimensional 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 v from different layers, which can be denoted asF * = [e -λ0t H (0) * , ..., e -λkt H (k) * ] ∈ R (k+1)×d R with * could be u or v. Then we concatenate them together to get F u,v = [F u , F v ] ∈ R 2(k+1)×d Rand obtain the raw pairwise feature fu,v by computing the inner product among different rows ofF u,v , which is fu,v = flat(F u,v F T u,v) with flat(•) means flatten a matrix of R 2(k+1)×2(k+1) into a vector of R 4(k+1) 2 . Finally, we feed the raw pairwise feature fu,v into an MLP to get the pairwise feature f u,v , which is f u,v = MLP(log(ReLU( fu,v ) + 1)). The ReLU(•) here is used to reduce estimation error, where the inner product of temporal walk matrices should be larger than zero and we thus set it to be zero if 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 +1 is the shift term to avoid the undefined value of log(0). We will see in Section 4.3 that these two operations can improve the training stability.Auxiliary Feature Learning. The auxiliary features such as link features also provide rich information 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 a sequential learning problem. Specifically, for node u, we take its recent m interactions S u = [({u, w 1 }, t 1 ), ..., ({u, w m }, t m )] before t and learn node embedding h u from this sequence. We first fetch the node featuresX u,N = [x w1 , ..., x wm ] ∈ R m×d N and edge features X u,E = [e t1u,w1 , .., e tm u,w1 ] ∈ R m×d E . For timestamps, we map the timestamps into temporal features [14] , where ϕ(∆t) = [cos(w 1 ∆t), .., cos(w d T ∆t)] is a time encoding function to learn the periodic temporal pattern. Besides, we construct a relative encoding sequenceX u,T = [ϕ(t-t 1 ), .., ϕ(t-t n )] ∈ R m×d T likeX u,F = [f u,w1 ⊕ f v,w1 , ..., f u,wm ⊕ f v,wm ] ∈ R m×8(k+1) 2to inject the pairwise features, where f u,wm denote the pairwise feature of u and w m 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 sequenceZ (0) u = MLP([X u,N , X u,E , X u,T , X u,F ]) ∈ R m×d .Subsequently, we stack l layers of MLP-Mixer [15] to capture the temporal and structural dependencies within the feature sequence, which isZ(l) u = Z (l-1) u + W (l) 1 GeLU(W (l)2 LayerNorm(Z (l-1)))EQUATIONFinally, we get the node embedding by mean pooling h u = MEAN(Zu ). The procedure to get node embedding h v 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 pt u,v = MLP([h u , h v , f u,v ]), where MLP(•) is a 2-layer MLP model with Sigmoid activation function in its output layer. 
experimental settings: 
 Datasets and Baselines. We conduct experiments on 13 benchmark datasets for temporal link prediction, 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.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 as the evaluation metrics. For dataset splitting, we chronologically split , where E is the number of the interactions. We find the best time decay weight λ via grid search within a range of 10 -4 to 10 -7 . Specifically, the best λ for Contact is 10 -4 , the best λ for MOOC, Can. Parl. and UN Vote is 10 -5 , the best λ for Wikipedia, Reddit, Enron, Social Evo., Flights and US Legis. is 10 -6 , the best λ for LastFM, UCI and UN Trade is 10 -7 .Implementatoin Details. For baselines, we use the implementation of DyGLib [9] , which is a unified temporal graph learning library, and has tuned the best hyperparameters for each baseline. For baselines that are not included in DyGLib (i.e., NAT and PINT), we use 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.Performance comparison among baselines. The performance of TPNet and baselines is shown in Table 1 . Due to space limit, Table 1 only shows the results under the transductive setting with random negative sampling strategy and more similar results can be found in Appendix G.1. 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 LastFM 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-wise methods, where TPNet achieves a 33× and 71.5× Scalability Analysis. To further verify the scalability of TPNet, we generated a series of random graphs with an average degree fixed at 100 and the number of edges varying from 1e5 to 1e8. Figure 4 shows the change of running time and GPU memory of TPNet, where the growth of 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-memory error when the edge number reaches 1e7 (shown inAppendix G.3), verifying the impracticability of explicitly storing temporal walk matrices.Proposed Components. To verify the effectiveness of the proposed components in 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. 3) w/o Scale that remove the log(•) and ReLU(•) in the pairwise feature decoding. As shown in Table 2 , there is a dramatic performance drop of w/o NR, which shows that the pairwise information carried by the node representations plays a vital role in the performance of TPNet. There is also an obvious performance drop of w/o Time, which confirms the necessity of 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 on 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 1 to 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 a main influence of the required dimension, where sparse graphs (like MOOC and Wikipedia) only need a small dimension, and dense graphs (like LastFM and Enron) may require a larger dimension. Empirically, setting the dimension to be 10 * log(2E) is 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 a 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 interactions in a 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 a 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-wise method was proposed, which constructs relative encodings as 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 are still far from satisfactory, where computation efficiency is a main concern and temporal information is seldom considered. In this paper, we unify existing relative encodings into a function of temporal walk matrices and explore encoding the pairwise information effectively and efficiently by temporal walk matrix projection. 
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 be optimal for networks characterized by long-term dependencies. Developing an adaptive matrix construction technique will be an interesting direction for future research. 
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 a unified function, which reveals a connection between the relative encoding and temporal walk matrix. Then we propose a new temporal link prediction model, TPNet, to address the computational inefficiencies and the ignorance of temporal information in 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. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 or 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). Guidelines:• The answer NA means that the authors have not 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., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [Yes]Justification: The proposed method does not have a high risk for misuse.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: In Algorithm 1 of NAT, it maintains a series of hash maps sEQUATIONu , .., s (k) u for each node u, which are sets of node ids. Next, we will first prove the statement holds if the size of the hash maps is infinite.Statement. s (i) is a set of nodes that u can approach through a temporal walk whose length is less than i + 1. u are set as empty set. The statement holds. When a new interaction ({u, v}, t) occurs and if the size of the hash maps is infinite, for 1 ≤ i ≤ k, the updating function of hash maps can be represented asEQUATIONwhere s(i) u and s(i)u denote the hash map after and before adding the interaction respectively. Then if the timestamp of ({u, v}, t) is larger than that of previous interactions, the newly generated temporal walks beginning from u must first visit v through ({u, v}, t) (proved in Section B.1), thus the newly added nodes that u can visit through a temporal walk with length less than i + 1 must belong to s(i-1) v. So s(i) u will contain all the nodes that u can approach through a temporal walk with length less than i + 1 after adding ({u, v}, t). The statement holds.For a node w, its similarity feature r w|u is a (k + 1)-dimensional vector, where for1 ≤ i ≤ k + 1, r w|u i = 1 if w ∈ s (i-1) uand r w|u i = 0 otherwise. Considering that the above statement holds, the similarity feature r w|u is equivalent to a (k + 1)-dimensional vector, where r w|u i = 1 if the shortest temporal walk from u to w is less than i; otherwise, rw|u i = 0. Algorithm 2: Temporal Walk Extraction (G(t), α, k, u)Initialize W to be {(u, t)} ; for i from 1 to k do (w p , t p ) ← the last (node, time) pair in W ; Sample one ({w p , w ′ }, t ′ ) ∈ E wp,tp with prob. ∝ exp(-α(t p -t ′ )) ;W i ← W i ⊕ (w ′ , t ′ ); Return W; A.2 CAWNFor constructing r w|u , CAWN first repeatedly samples m temporal walks of length k begging at u according to the sampling strategy in Algorithm 2. Then r w|u is set to be a (k + 1)-dimensional vector, where r w|u i will be the number of walks whose i-th visited node is w for 1 ≤ i ≤ k + 1, which can be represented as,EQUATIONwhere W j is the j-th sampled walks and1 Wj [i][0]=w is 1 if W j [i][0] = w; otherwise, 1 Wj [i][0]=w is 0. Due to each temporal walk being sampled independently, 1 W1[i][0]=w , • • • , 1 Wm[i][0]=w are m independent and identically distributed Bernoulli random variables Ber(µ i-1 w ), where µ i-1 w is the probability of reaching w from u after performing a (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., 1m m j=1 1 Wj [i][0]=w ⇐⇒ 1 m r w|u i) will coverage to the mean as the number of sampled walks m → ∞. The mean of the Ber(µ i-1 w ) is µ i-1 w . Expand all (i -1)-step temporal walks from u to w, we haveEQUATIONTimestamps: 𝑡 1 < 𝑡 where f (•) is the sampled probability of a walk according to Algorithm 2. For Algorithm 2, if we are current at (w i , t i ), then the probability of moving to (w i+1 , t i+1 ) through an interaction({w i , w i+1 }, t i+1 ) is proportional to exp(-α(t i -t i+1 )), which is exp(-α(ti-ti+1)) (w ′ ,t ′ )∈E w i ,t i exp(-α(ti-t ′ )). Thus the probability of a temporal walk W = [(w 0 , t 0 ), (w 1 , t 1 ), .., (w k , t k )] isEQUATIONwhich is the same as the score function s ′ (•) of CAWN we shown in Section 2.2.2. Thus, r w|u i(multiplied with a const 1 m ) is the same as W ∈M i-1 u,w s ′ (W ).The equation in Theorem 1 can be rewritten as H (l) (t) = e λlt * A (l) (t)P . We can consider e λlt * A (l) (t) as a new temporal walk matrix whose score function for a temporal walk [(w 0 , t 0 ), (w 1 , t 1 ), ..., (w l , t l )] at time t is e λlt * s(W ). Expanding it, we have We use the notation Ā(l) (t) to denote e λlt * A (l) (t) and s(W ) to denote e λlt * s(W ) for a lstep temporal walk in the following proof. The original problem is transformed into proving that H (l) (t) = Ā(l) (t)P . Note that for a given temporal walk [(w 0 , t 0 ), (w 1 , t 1 ), ..., (w l , t l )], each term of s(W ) (i.e., l j=1 e λtj ) will no change as time t goes on. Thus the temporal walk matrices Ā(l) (t) will only change when a new interaction occurs. Next, we inspect how the Ā(l) (t) changes when a new interaction (u, v, t) occurs. For each element Ā(l) i,j (t), its change is caused by the newly generated l-step temporal walks from i to j after adding the interaction (u, v, t), which can be written asEQUATIONwhere t + denotes the timestamps right after t and ∆M l i,j denote the newly generated l-step temporal walks from i to j. According to the definition of the temporal walk, the new lstep temporal walks must begin from u or v. Because if there is a temporal walk that does not begin from u or v, it can be represented as [(w 0 , t 0 ), .., (w i , t i ), (u, t i+1 ), (v, t), .., (w l , t l ))] or [(w 0 , t 0 ), .., (w i , t i ), (v, t i+1 ), (u, t), .., (w l , t l ))], which means that there is an interaction ({w i , u}, t i+1 ) or ({w i , v}, t i+1 ) whose timestamp t i is larger than t. (Since the timestamps of a temporal walk are decreasing). This is impossible since (u, v, t) is a newly happened interaction. Thus only the u-th row and v-th row of the Ā(l) (t) will change. Besides for each newly generated temporal walk from u, it must be [(u, t), (v, t 1 ), .., (w l , t l ))], where [(v, t 1 ), .., (w l , t l ))] corresponds to a (l -1)-step temporal walk beginning from v. And for any (l -1)-step temporal walk beginning from v, we can add a prefix (u, t) to make it become a l-step temporal walk beginning from u. Thus for any 1 ≤ i ≤ n, there is a one-to-one mapping between ∆M l u,i and M l-1 v,i (t) with M l-1 v,i (t) denote the set of (l -1)-th temporal walks from v to i before t, and we can rewritten Equation (12) asEQUATIONThe updating function for Ā(l) v,i (t) is also similar. We give a visual illustration of the new temporal walks in Figure 6 for better understanding. Finally, writing the update formula in vector form, for anyEQUATIONwhich is the same as Equation ( 14)! Thus if H (l) (t) = Ā(l) (t)P for 0 ≤ l ≤ k, after adding a new interaction (u, v, t), for 0 ≤ l ≤ k, H (l) (t + ) = Ā(l) (t + )P still holds. Because we haveEQUATION) Note that the equation in Equation (1) holds at initialization, thus the equation always holds and the theorem is proved.The Theorem 2 can be considered as a special case of the Johnson-Lindenstrauss 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 1 ((Lemma 3.18 of [26] )). Let x ∈ R d be a d-dimensional random vector whose entries are independent N (0, 1 d ). Then for any ϵ ∈ [0, 1],EQUATIONThe 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.Based on the above lemma, we can get the following corollaries. Corollary 1. Given any ϵ ∈ (0, 1), x ∈ R m . Let P ∈ R d×m be a random matrix whose entries are independent N (0,EQUATIONProof. For the above corollary, we haveEQUATIONNote that each entry of P is an independent N (0, 1 d ), thus P x is a random vector whose each entry(P x) k = m i=1 P k,i * x i is an independent N (0, ∥x∥ 2 2 d) and each entry of P x ∥x∥2 is an independent N (0, 1 d ). Substituting it to Lemma 1 and taking d ≥ 8 ϵ 2 log( 1 δ ), we haveEQUATIONBased on Corollary 1, we can get the following corollary.Corollary 2. Given any n m-dimensional vectors x 1 , ..., x n , ϵ ∈ (0, 1), let P ∈ R d×m be a random matrix whose entries are independent N (0, 1 d ), if d ≥ 24 ϵ 2 log(4 1/3 n), for any 1 ≤ i, j ≤ n, we haveEQUATIONlet E + i,j and E - i,j denote the event of { ∥P (x i + x j )∥ 2 2 -∥x i + x j ∥ 2 2 ≤ ϵ∥x i + x j ∥ 2 2 } and { ∥P (x i -x j )∥ 2 2 -∥x i -x j ∥ 2 2 ≤ ϵ∥x i -x j ∥ 2 2 }respectively. Since x i + x j and x i -x j can also be consider two m-dimensional vectors. Thus take it and d ≥ 24 ϵ 2 log(4 1/3 n) into Corollary 1, we haveP(E + i,j ) ≥ 1 -1 2n 3 and P(E - i,j ) ≥ 1 -1 2n 3 . Then let C i,j = E + i,j ∩ E - i,j denote that E + i,jand E - i,j hold simultaneously, according to the union bound, we haveEQUATIONwhere E + i,j denote that E + i,j does not hold and E + i,j ∪ E - i,j denotes that E + i,j or E - i,j holds. According to the union bound, we further haveEQUATIONwhere ∩ i,j C i,j denote that C i,j holds for any i, j and ∪ i,j C i,j denote that there exist i, j that C i,j holds. If C i,j holds, we haveEQUATIONMultiplying Equation ( 24) with -1 and adding it to (23), we haveEQUATIONThus we haveEQUATIONholds for any 1 ≤ i, j ≤ n.The matrix of A (l) (t) in Theorem 2 can be considered as n vectors with n dimensions, where each row of A (l) (t) is a n-dimensional vector. Similarly, we can consider A (0) (t), • • • , A (k) (t) together as n(k + 1) vectors with n dimensions. Considering that P ∈ R n×d R is a random matrix where each entry is an independent N (0, 1 d R ) and e -λlt * H (l) (t) is the projection of A (l) (t), substitute it into Corollary 2 and taking the number of vectors as (k + 1)n, we can get Theorem 2.For the situation where multiple interactions happen simultaneously, we can first compute each interaction's contribution independently and sum them together to update the node representations. The maintaining mechanism is shown in Algorithm 3, where we packed the interactions that happen at the same time into a set B and sum the independent contribution of each interaction in B into ∆H (1) , • • • , ∆H (k) . For simplicity, we initialize ∆H (1) , • • • , ∆H (k) each time and it can be replaced by some efficient implementation such as scatter_add operation in pytorch. Initialize H (0) , H (1) , ..., H (k) ∈ R n×d R as zero matrix ; Fill H (0) with entries independently drawn from N (0, 1 d R ) ; for B ∈ G do Initialize ∆H (1) , ..., ∆H (k) ∈ R n×d R as zero matrix ;for (u, v, t) ∈ B do for l = k to 1 do 7 ∆H (l) u = ∆H (l) u + e λt * H (l-1) v ; 8 ∆H (l) v = ∆H (l) v + e λt * H (l-1) u ; for l = k to 1 do H (l) = H (l) + ∆H (l) ;Return H (0) , H (1) , .., H (k) ;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 to handle the situation where multiple interactions happen simultaneously. For the updating of other types of temporal walk matrices, let k+1)×d 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.A(t) = [A (0) (t), • • • , A (k) (t)] ∈ R n(Condition 1. After adding a new interaction (u, v, t), the change of each row can be written as the linear combination of other rows, which is for each 1 ≤ i ≤ n(k + 1), there exists k 1 , ..., k m and l 1 , ..., l m satisfying.A i (tEQUATIONwhere t + is the time right after t. Condition 2. After time moving ∆t without adding new interactions, the change of each row can be written as the linear combination of other rows, which is for each 1 ≤ i ≤ n(k + 1), there exists k 1 , ..., k m and l 1 , ..., l m satisfying.EQUATIONThe motivation behind the conditions is that the projection is a linear operation. If the node representations are the projection of the temporal walk matrix at t (i.e.,H(t) = A(t)P ) and the updating function of the temporal walk matrix is the linear combination of other rows, then we can apply the same updating function on H(t), which will make H(t + ) still be the projection of the temporal walk matrix. For example, applying (27) to H(t) will getEQUATION= (k 1 A l1 (t) + • • • + k m A lm (t))P = A i (t + )PThen we can ensure that H(t) is always the random projection of A(t) and thus preserve the inner product of the A(t).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 (l) u,v (t) is the number of the l-step temporal walks from u to v and their feature propagation mechanism is shown in Algorithm 4, where the obtained node representations are the projection of the corresponding temporal walk matrix.For CAWN, its score function for a temporal walk W = [(w 0 , t 0 ), (w 1 , t 1 ), ..., (w l , t l )] is defined as s(W ) = l-1 i=0 exp(-α(ti-ti+1))({w ′ ,w},t ′ )∈E w i ,t i exp(-α(ti-t ′ )) . As time goes on, its element of temporal walk Algorithm 4: Propagation Mechanism for DyGFormer (G,k,n,d R ) Initialize H (0) , H (1) , ..., H (k) ∈ R n×d R as zero matrix ; Fill H (0) with entries independently drawn from N (0,1 d R ) ; for (u, v, t) ∈ G do for l = k to 1 do H (l) u = H (l) u + H (l-1) v ; H (l) v = H (l) v + H (l-1) u ;Return H (0) , H (1) , .., H (k) ;Algorithm 5: Propagation Mechanism for CAWN (G,α,k,n,d R )Initialize H (0) , H (1) , ..., H (k) ∈ R n×d R as zero matrix ; Fill H (0) with entries independently drawn from N (0,1 d R ) ; Initialize d ∈ R n as zero vector ; Set t prev ∈ R to be zero ; for (u, v, t) ∈ G do d = d * exp(-α(t -t prev )) ; for l = k to 1 do H (l) u = du du+1 * H (l) u + 1 du+1 * H (l-1) v ; H (l) v = dv dv+1 * H (l) v + 1 dv+1 * H (l-1) u ; d u = d u + 1 ; d v = d v + 1 ; t prev = t ;Return H (0) , H (1) , .., H (k) ; matrices will not change. When a new interaction (u, v, t) happens, for a temporal walk matrix A (l) (t), its u-th row and v-th row will change. Formally, let d(t) ∈ R n denotes a time decay degree vector, where for each node u, d u (t) is defined as d u (t) = ({(u,v ′ },t ′ )∈Eu,t exp(-α(t ′ -t)) with E u,t denoting the set of interactions attached to u before t, then the updating function of the temporal walk matrix A (k) (t) can be represented asEQUATIONwhere du(t) du(t)+1 * A (t) correspond to change caused by the newly generated l-step temporal walk from u (the same for v and similar analysis about the updating of temporal walk matrix can be found in Appendix B.1). Then we can give the propagation mechanism for CAWN in Algorithm 5 based on the above analysis, where d corresponds to the time decay degree vector.We proposed an effective and efficient temporal link prediction method, which may advance realworld 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 to imbalanced outcomes such as reduced diversity in recommendation systems.Experiments are conducted on the following 13 benchmark datasets3 collected by [16] .• Wikipedia is a bipartite interaction graph that records the edits on Wikipedia pages over a month. Nodes represent users and pages, and links denote the editing behaviors with timestamps. Each link is associated with a 172-dimensional Linguistic Inquiry and Word Count (LIWC) feature [27] . • Reddit is a bipartite graph capturing user posts under subreddits over a month. Nodes represent users and subreddits, while links denote timestamped posts. Each link carries a 172-dimensional LIWC feature. • MOOC is a 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 a bipartite network detailing song-listening behaviors of users over one month.Nodes are users and songs, and links represent listening activities. The weight of each link represents the total normalized agriculture import or export values between two countries. • UN Vote records roll-call votes in the United Nations General Assembly. A link between two nations increases in weight each time both vote "yes" on an item. • Contact tracks the evolution of physical proximity among approximately 700 university students over a month. Each student has a 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.We select the following eleven popular baselines:• JODIE [3] designs a recurrent architecture to maintain a memory vector for each node and a projection layer to map the node memories into future representation trajectories. • DyRep [28] considers each link as a temporal point process [29] and designs a deep temporal point process model to capture the dynamics of the observed process. • TGAT [14] proposes a 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 a general framework for temporal graph learning, which includes a 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 a 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 a statistical method, that gives the likelihood of a link based on historical interactions between the two end nodes. • TCL [32] propose a graph transformer architecture [33] to 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 a series of N-caches to store the neighborhood information and use them to decode the pairwise information between nodes. • PINT [8] proposes an injective temporal message passing mechanism to learn node representations 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 employs MLP-Mixer to learn the representation of a node from its historical interaction sequences. • DyGFormer [9] proposes a 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.The results under other settings are shown in Table 6 , Table 7 , Table 8 , Table 9 and Table 10 .Efficiency analysis results on Reddit, UCI, and Wikipedia are shown in Figure 7 .The scalability analysis result of PINT is shown in Table 4 , where OOM indicates the out-of-memory error.Figure 7 : Efficiency analysis on more datasets. Results on Wikipedia, Enron, and UCI are shown in Figure 8 .Table 5 shows the mean of node representation norm at different layers, where aEb indicates a × 10 b . • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It 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 a 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 or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.For memory-based methods (i.e, TGN), X N u,k represents the concatenation of node memories and features.https://zenodo.org/record/7213796#.Y1cO6y8r30o 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: The authors discussed the limitations of the model in the appendix.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1、If the authors could provide a comparison of memory usage, it would make the model more convincing.

2、This paper does not provide an analysis of the impact of different functions g on relative encoding.

3、The author did not compare with the latest models (published in AAAI 2024 or WWW 2024) in Table 1.
questions: questions: please see weaknesses
limitations: limitations: n/a
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The limitations of the approach are only briefly discussed in the appendix.
2. 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.

Minor points / text linting suggestions:

Line 81: What is a "unified formation", did you mean "formulation"?

Line 94: Style "all the interactions happen" -> "all the interactions that happen"

Line 128: Doesn't A^(i) aggregate the i-step temporal walks, instead of k-step? Typo?

Line 187: "The value of score function.." -> "The value of the score function".

Line 202: What is d? The node degree or dimensionality? Please define. Also in line 2, Algorithm 1.

Line 203: Typo enumerating the H vectors. The index 1 is repeated, whereas it should be followed by 2.

Line 205: Style "Pseudocode code" -> "Pseudocode"

Line 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.

Line 261: "and obtained" -> "and obtain"
questions: 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.

2. 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?

3. 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.

```{python}
set(random.sample(test_node_set, int(0.1 * num_total_unique_node_ids)))
```
Had to be changed to:
```{python}
set(random.sample(sorted(test_node_set), int(0.1 * num_total_unique_node_ids)))
```
		
This happened installing your code in a new python 3.12 environment.
limitations: limitations: The limitations are briefly discussed in the appendix.

Comments: title: Response to Reviewer SMMz
Response
Response to Reviewer YNEN
Response to Reviewer vApy
comment: Thank you for your reply. We are pleased to hear that you have no further concerns.
Thanks the authors for the rebuttal, and I have no more concerns.
Thanks again! We sincerely appreciate your timely reply and support for our work.
Thank you for your response and clarifications.

As it stands, I have no more outstanding concerns, and am happy to give this work an Accept.
Thank you for your timely reply! We sincerely appreciate your support for our work.
Thank you for the detailed response. I’ve read it and you’ve clarified my doubt, so I’ve increased my score.