Improving Temporal Link Prediction via Temporal Walk Matrix Projection

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.

Q1 Line 265: Why does ReLU reduce estimation error? Is this an empirical result, or an architectural consideration specific to your data? Please clarify.

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

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?

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

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

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.

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

W1 The limitations of the approach are only briefly discussed in the appendix.

We will move the limitation section into the main body of our paper and expand the discussion.

W3 Minor points / text linting suggestions

We have revised the paper according to your suggestions for lines 81, 94, 187, 203, 205, 211, and 261.

For line 128: Yes, it is a typo, and we will correct it.

For line 202: $d$ indicates the dimensionality, and we will replace it with $d_R$.

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.

W1. If the authors could provide a comparison of memory usage, it would make the model more convincing.

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

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

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

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

W3. The author did not compare with the latest models (published in AAAI 2024 or WWW 2024) in Table 1

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

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

As shown in the above table, TPNet is more computationally efficient than FreeDyG, achieving at least a 4.52 $\times$ speedup.

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

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.

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

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

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.

We 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):

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.