TAMI: Taming Heterogeneity in Temporal Interactions for Temporal Graph Link Prediction

Thank you very much for the constructive feedback. Below we respond to the concerns raised.

• W1. The technical contribution of this paper is limited, as the proposed modifications are trivial and their effects are expected. Specifically, the LTE method introduces a log transformation to the temporal differences — a well-known technique in machine learning to improve the training stability when the feature scales vary. As such, it is unsurprising that this modification improves model performance when the scales of temporal differences vary

Thanks for the thoughtful comment. We believe that the reviewer's assessment that our modules' effects were as expected, and the performance improvement was unsurprising, confirms the intuitive and effective nature of our design.

We emphasize that our design is novel and our contributions are substantial. Specifically, we are the first to identify the heterogeneity in temporal interactions and investigate its impact on the performance of TGNNs thoroughly. This heterogeneity leads to two problems in temporal link prediction for existing TGNNs, i.e., ineffective temporal encoding and forgetting of past interactions for a pair of nodes that interact intermittently. To cope with these problems, we propose two novel modules, namely, LTE and LHA, respectively. We then develop an end-to-end framework named TAMI to integrate LTE and LHA into existing TGNNs to boost their performance in temporal link prediction. Extensive experiment results on 13 classic datasets and 3 large TGB datasets demonstrate the effectiveness of TAMI.

In particular, while the logarithmic transformation is a well-known technique in statistics and machine learning, it remains unknown why and where we need to apply it to TGNNs. LTE is motivated by our observation that temporal differences often follow a highly right-skewed distribution, but existing TGNNs overlook this skewness. Since their time encoding functions are directly applied to the raw temporal differences, their resulting models often struggle with the prediction of infrequent interactions, as shown in Figure 3(b). LTE addresses these issues by transforming a skewed distribution of temporal differences into a more balanced one, thereby effectively improving the link prediction accuracy.

• W1 (cont'd) The instability of temporal encoding methods was previously discussed in GraphMixer.

Thanks for the comment. Our work is orthogonal to GraphMixer. GraphMixer finds that the instability of time encoding functions is due to the fact that the gradients of their trainable parameters scale proportionally with the input temporal differences. Thus, they propose to fix these parameters during training. In contrast, in TAMI, we observe a new problem that the distribution of the input temporal differences is often right-skewed, and its negative impact on temporal link prediction. Based on this observation, we propose a novel time encoding function, LTE, to directly mitigate the skewness in the temporal differences to improve the link prediction performance. Note that LTE can be used for both when the frequency parameters need to be learned or fixed.

As such, LTE can be integrated into GraphMixer to boost its performance. As shown in Figure 3(b), together with LTE, GraphMixer's performance improves substantially, especially for node pairs whose interaction intervals are long. Furthermore, Tables 3 and 16 in our manuscript show that LTE, used with the fixed time encoding function in GraphMixer, consistently improves GraphMixer's performance under both transductive and inductive settings.

• W1 (cont'd) LHA stores more historical embeddings instead of just the most recent one to mitigate information loss. Similar ideas have been explored in prior work [3].

Thanks for the comment. Again, our work is orthogonal to [3]. Our LHA module maintains the historical interactions using edge embeddings for each target node pair, in addition to the node embeddings learned by the underlying TGNN, such as [3], which retains each node's recent historical interactions to learn its temporal node embeddings.

Suppose we are to predict a link between node $u$ and node $v$. [3] first computes the temporal node embeddings of $u$ and $v$ using $u$'s recent interactions and $v$'s recent interactions, respectively. However, it is possible that $u$ and $v$ do not interact recently. Hence, their node embeddings may not capture any of their interaction history and thus be less effective in link prediction. In contrast, LHA explicitly encodes the past interactions between $u$ and $v$ into a dedicated historical edge embedding and directly leverages this edge embedding, together with their node embeddings, for predicting their future link.

[3] Cheng K, Linzhi P, Ye J, et al. Co-Neighbor Encoding Schema: A Light-cost Structure Encoding Method for Dynamic Link Prediction. ACM KDD 2024.

• W2. The experimental evaluation lacks comprehensiveness and fails to convincingly support the claimed advantages of the proposed method

Thanks for the comment. Our experimental evaluation is comprehensive and extensive, as it is done with various underlying TGNNs on 13 classic datasets and 3 large TGB datasets under both inductive and transductive settings with three negative sampling strategies.

Furthermore, the effectiveness of LTE and LHA is demonstrated separately. The effectiveness of LTE in mitigating the skewness in temporal differences for improved link prediction accuracy is well supported by Figure 3(b) and Tables 3, 13, 16, and 18 in our manuscript. In addition, the effectiveness of LHA in addressing the forgetting issue of historical interactions between target node pairs for improved link prediction accuracy is well demonstrated by Figures 5, 8, and 9, and Tables 3, 13, 16, and 18.

• W2 (cont'd) Authors are supposed to report the results of TAMI on newer methods, like [1], for a fair and thorough evaluation of the proposed TAMI method

Thanks for the comment. We do not aim to propose yet another TGNN architecture. Instead, we propose TAMI to be used for existing TGNNs to further improve their performance by addressing the heterogeneity of temporal interactions that is overlooked in their learning process. We demonstrate the effectiveness of TAMI through extensive experiments. For example, Tables 1, 2, and 5 in our manuscript show that TAMI consistently improves the performance of various TGNNs over their vanilla counterparts.

To provide a more thorough evaluation, we have conducted extra experiments on TAMI with TPNet [1]. As shown in Table 1 below, TAMI indeed improves the performance of TPNet.

Table 1: Transductive AP of TPNet with and without TAMI.

[1] Lu X, Sun L, Zhu T, et al. Improving Temporal Link Prediction via Temporal Walk Matrix Projection. NeurIPS 2024

• W2 (cont'd) The efficiency analysis is limited to two small datasets (i.e., UC and EN) and one computationally expensive baseline

Thanks for the comment. In Section 4.6, we do not aim to evaluate the computational efficiency of TAMI, but rather to empirically demonstrate that TAMI can improve the training efficiency of underlying TGNNs. As shown in Figure 6, TAMI enables DyGFormer, GraphMixer, and TGAT to converge faster than their vanilla counterparts, while achieving higher validation average precision with fewer training epochs. We have also conducted similar experiments for three other baselines, i.e., TGN, JODIE, and CAWN. Results in Table 2 below show that TAMI indeed improves their training efficiency. The overall trend of training three new baselines is similar to our observation with Figure 6.

Table 2: Results on the UC (top) and EN (bottom) dataset.

In addition, in Figure 7, we demonstrate that TAMI enables existing TGNNs, such as DyGFormer, to compute temporal node embeddings using fewer historical interactions to achieve comparable or even better performance. As a result, they consume much less GPU memory during training, require less training time per epoch, and converge faster with fewer epochs. We here use DyGFormer as an example because it is the top performer in all baselines. Together with TAMI, this computationally expensive baseline becomes much more efficient while achieving comparable or even better performance, with less GPU memory usage (up to 53.22%) and less training time per epoch (up to 40.54%).

We have conducted additional experiments on the large-scale dataset, UNVote (UV), which contains over one million edges, using DyGFormer and CAWN. Results are shown in Table 3 below. Again, TAMI allows them to use significantly fewer historical interactions to achieve comparable or even better performance, thereby reducing both GPU memory usage and total training time.

Table 3: Results on the UV dataset. The number in the parenthesis indicates the number of historical interactions used to compute the node embeddings.

We thank the reviewer for recognizing our paper with precise formula definitions, well-formulated problem hypotheses, rigorous mathematical proofs, and extensive comparative and ablation experiments as well as being the first to identify heterogeneity in continuous-time temporal graph interactions and its impact on link prediction performance. Below, we respond to the concerns raised.

• W1. In Figure 4, when describing historical interactions between node pairs, node v5 appears twice as an interaction node for node u, which may be a typographical error and warrants author clarification

Thanks for pointing this out. We will update the figure to use two links, instead of two nodes, to represent the two interactions between node $u$ and node $v_5$ for better clarity.

As you may have noticed, our intention behind Figure 4 was to show that a target node may engage in frequent interactions with a small set of nodes, dominating its recent interaction history. For example, a student may have hamburgers on both Monday and Tuesday, resulting in two distinct links between the "student" node and the "hamburger" node, each associated with a different timestamp. In this case, node $u$ frequently interacts with node $v_5$ at timestamps $t_3$ and $t_4$. As a result, historical interactions between the target node pair, i.e., node $u$ and node $v$, may be forgotten in their latest temporal node embeddings, thereby leading to degraded link prediction accuracy.

• W1 (cont'd). The paper does not discuss limitations or shortcomings of the proposed method

Thanks for the comment. We would like to point out that the limitations are discussed in Appendix C.3.

• W1 (cont'd). Although the authors conducted thorough experiments, they did not clarify whether the hyperparameter in Equation (4), used to measure the forgetting rate of historical interactions, varies across different datasets; if so, further explanation is needed.

Thanks for the comment. We would also like to point out that the setting of $\gamma$ in Equation (4) is mentioned in the section Implementation Details in Appendix B.3. We set $\gamma = 0.9$ for most experiments. In addition, we examine the performance of underlying TGNNs with different values of $\gamma$ and present the results in Table 14 under the section Analysis of the Hyperparameter $\gamma$ in LHA in Appendix C.4.

• Q1. In Section 4.6, the authors state that "UC and EN datasets require only 2 and 32 historical interactions for attention calculation", indicating that the choice of the number of historical interactions (k) varies across datasets. Is this variation related to dataset characteristics such as sparsity, scale, or interaction depth?

Thanks for the comment. We would like to clarify that the number of historical interactions discussed here is not the same as the number of historical edge embeddings ($k$) stored and used in our LHA module. The value of $k$ is set to 1 and remains fixed in the experiments. Existing TGNNs (e.g., GraphMixer and DyGformer) utilize historical interactions of a node to compute its temporal node embedding. However, in addition to those node embeddings, TAMI stores and leverages $k$ historical edge embeddings in LHA to ensure that the mutual interaction history between a target node pair is preserved when predicting their future links. Figure 7 in Section 4.6 demonstrates that, when integrated with TAMI, the underlying TGNN (e.g., DyGformer) can compute temporal node embeddings based on significantly fewer historical interactions compared with its vanilla counterpart, i.e., from 256 to 32 on the EN dataset and from 32 to 2 on the UC dataset, to achieve comparable or even better performance.

• Limitations: The authors’ contributions focus on improving temporal encoding and information aggregation, offering a novel perspective and effectively enhancing existing models. However, the approach lacks methodological innovation, resulting in somewhat limited overall contributions

Thanks for the thoughtful comment. We would like to point out that we are the first to identify the presence of heterogeneity in temporal interactions and investigate its impact on the performance of TGNNs thoroughly. This heterogeneity leads to two problems in temporal link prediction for existing TGNNs, i.e., ineffective temporal encoding and forgetting of past interactions for a pair of nodes that interact intermittently. To cope with these problems, we propose two novel modules, namely, LTE and LHA, respectively. We then develop an end-to-end framework named TAMI to integrate LTE and LHA with various types of existing TGNNs in order to boost their performance in temporal link prediction. In other words, we do not propose yet another TGNN, but we propose TAMI to be used as an add-on to existing TGNNs for improved temporal link prediction. Comprehensive and extensive experiment results on 13 classic datasets and 3 large TGB datasets with three negative sampling strategies under both inductive and transductive settings demonstrate the effectiveness of TAMI.

We hope this clarifies the motivation and the contributions of our work, and we sincerely appreciate the reviewer’s comment.

We thank the reviewer for recognizing our work with clear motivation that is effectively supported, our framework as light-weight and easily implemented. Below we respond to the concerns raised.

• (O1) In Section 3.3, the authors state that LHA uses most-recent aggregation. This effectively renders the parameter k redundant, as only a single historical interaction is considered regardless the value of k. Intuitively, using a larger k should enhance the performance of TAMI by incorporating more historical context. Therefore, additional experiments should be conducted with varying values of k, as well as alternative aggregation functions such as sum, which would make practical use of multiple historical interactions.

Thanks for the comment. We respectfully disagree that only a single historical interaction is considered. We use an exponentially weighted moving average as in Equation (4) of the manuscript to compute the dedicated edge embedding for a given target pair of nodes. Thus, even if $k=1$, LHA considers all the interaction history between the pair of nodes. Varying $k$ values only controls how much freshness of information for the pair of nodes we maintain with a higher weight in the exponentially weighted moving average.

In Table 1 below, we show the results of additional experiments to evaluate the performance of TAMI with different $k$ values and aggregation functions. Overall, the performance of different variants of TAMI is better than the vanilla version (without TAMI), indicating the effectiveness of our design. It is also important to note that larger $k$ value does not necessarily lead to better performance. This is expected as different datasets may have different levels of dependency on the interaction history for temporal link prediction. In addition, TAMI is not sensitive to the choice of aggregation functions.

Table 1: Test AP of DyGFormer on the EN and CP datasets with different $k$ values and aggregation strategies.

• (O2) Some experimental results require more detailed interpretation. As shown in Table 11, datasets CO, LA, and SE exhibit higher skewness. However, Table 1 shows that the performance improvement obtained from TAMI on these datasets are relatively modest. Notably, the SE dataset, despite having a skewness over 140, shows less than 2% performance improvement, which is significantly lower than the improvements observed on other datasets. This finding appears to contradict the motivation that TAMI should be especially effective on highly skewed datasets. The authors should provide a deeper explanation for this discrepancy.

Thank you very much for this insightful comment. We respectfully argue that the performance gains achieved by TAMI on the CO and LA datasets are satisfactory. On the LA dataset, GraphMixer with TAMI improves by up to 16.64%, while DyGFormer with TAMI improves by up to 2.24% among all the three negative sampling strategies. Likewise, on the CO dataset, GraphMixer with TAMI improves by up to 5.77%, while DyGFormer with TAMI improves by up to 3.93%. These results all demonstrate the effectiveness of TAMI.

For SE (SocialEvo), we have looked into the dataset carefully and found that the high skewness is caused by a two-mode distribution. As shown in Table 2 below, one mode takes almost all the temporal differences while the other mode consists of only few ones (0.002%). There are no values between the two modes. This is due to the nature of the dataset. It is a mobile phone proximity network that captures daily interactions among students living in a dormitory over eight months. Temporal edges are formed between two students when they interact with each other via mobile phones. Hence, most interactions occur daily, but there are a few interactions that take place after more than two months, probably summer breaks, leading to ultra large temporal differences compared with the others. Even in this extreme case, TAMI can still bring an improvement by balancing the distribution, again showing the effectiveness of our design.

We hope this clarifies and thanks again for the reviewer's meticulous review.

Table 2: The distribution of temporal differences on the SE dataset exhibits a bimodal pattern, with 99.998% of the temporal differences being less than 19.67 days.

• (O2) (cont'd). Besides, the skewness of TGB generated datasets should also be reported.

Thanks for the suggestion. We report the original skewness of temporal differences in the TGB datasets and the skewness after applying our LTE in Table 3 below. Results show that our LTE effectively reduces the skewness in the distribution of the temporal differences.

Table 3: Skewness of temporal differences before and after applying our LTE on the three TGB datasets tested

• (O3) Similarly, in Figure 5, the performance improvement achieved by LHA on exclusive nodes for datasets EN and UC is smaller than improvement achieved on isolated and mutual nodes. Intuitively, one would expect LHA to yield the most significant improvement on exclusive nodes. The authors should provide additional insights or analysis to clarify why LHA appears less effective on exclusive nodes in EN and UC compared to the other two datasets.

Thanks for the comment. The performance improvement achieved by LHA on exclusive nodes is smaller than that on isolated and mutual nodes in the EN and UC datasets. This is because most exclusive target node pairs have no interaction prior to prediction, resulting in empty LHA memory at prediction time, as shown in Table 4 below. For example, 89.67% of the exclusive target node pairs in the UC dataset have not interacted with each other during training. This is possible as the edges in the UC dataset are formed by messages sent between students on some social media. Many students may only interact once if they are not familiar with each other, which is used for their link prediction in testing. Without historical information stored, LHA cannot contribute to these predictions, leading to limited or no performance gains. However, all isolated and mutual node pairs have interacted at least once during training, allowing LHA to store and utilize historical interactions between target node pairs and thus improve performance.

The case for exclusive node pairs from the UC dataset can also be treated as a special case of the cold start for LHA, which is studied in Appendix C.6 in the manuscript. As shown in Figure 9 in the manuscript, if we have more interaction events between target node pairs, the performance gain will be larger.

Table 4: Proportion of node pairs that do not have any interaction in training set

We thank the reviewer for recognizing our design choices as theoretically motivated and our experiments as extensive. Below we respond to the concerns raised.

• W1. No experiments on other dynamic graph tasks (e.g., dynamic node classification)

Thanks for the comment. We would like to clarify that our TAMI framework is specifically designed for the temporal link prediction task, which is the main downstream task in TGNNs. We observe that temporal interactions are heterogeneous, e.g., a few node pairs can make most interaction events, and interaction events happen at varying intervals. This can significantly degrade the link prediction performance of existing TGNNs, especially when predicting the links for infrequently interacting node pairs. Thus, we develop the TAMI framework to mitigate the heterogeneity issue in temporal interactions and in turn improve the link prediction accuracy. While it is beyond the scope of this work to extend TAMI to other dynamic graph tasks, such as dynamic node classification, we believe it is a promising direction for our future work.

• W2. Less improvement in the inductive setting and for balanced datasets where the temporal differences roughly follow a normal distribution.

Thanks for the thoughtful comment. For the inductive setting, it is similar to the case discussed in the section Cold Start of LHA in Inference in Appendix C.6. Specifically, the target node pairs in testing may not be observed during training. Hence, LHA's memory may need to be constructed from scratch during the test phase. At the beginning of the test phase, LHA contains no historical information for some node pairs, limiting its effectiveness and leading to smaller performance gains. However, as the test phase progresses and more interaction events are accumulated, LHA becomes more and more effective, resulting in higher performance gains.

In addition, as shown in Table 11 in Appendix B.5, most of the datasets exhibit skewness (or heterogeneity in temporal interactions). TAMI is designed to tackle the problems associated with this skewness. Hence, when integrated into TAMI, the performance of underlying TGNNs improves substantially for most cases. For few balanced datasets, the performance gain from TAMI may not be as significant as the one with skewed datasets, but TAMI still enables underlying TGNNs to achieve better performance than their vanilla counterparts. This is somewhat expected because the skewness is mild in the balanced datasets. Nonetheless, many real-world datasets exhibit high skewness.

• W3. The LTE and LHA modules have minor improvements for some models (e.g., DyGFormer). No provided intuition as to why this occurs.

Thanks for the comment. DyGFormer is the top performer in all the baselines. It achieves state-of-the-art performance by leveraging the attention mechanism across almost all (up to 99%) historical interactions of a node to learn its node embedding. However, this comes at the cost of high GPU memory consumption and slow convergence speed. As demonstrated in Section 4.6, when integrating DyGFormer into our TAMI framework, we are not only able to reduce its GPU memory usage (by 53.22%) and improve its convergence speed (by 40.54%) by leveraging much fewer (16$\times$ fewer) historical interactions of a node, but still improve the performance compared with its vanilla version. This is thanks to LTE, our effective time encoding function to mitigate the skewness of the temporal differences, and LHA for explicit encoding of interaction history of the target node pairs in temporal link prediction.

We also present the ablation study for the historical (hist) and the inductive (ind) negative sampling strategies in the following table. The results confirm the effectiveness of both modules.

Table 1: Test AP for transductive link prediction.

• Q1. [1] has found simple linear time encoding functions to be more effective than the sinusoidal function used in your work. Can the linear time encoding function benefit from your module?

Thanks for the comment. Yes, the linear time encoding function proposed in [1] can also benefit from our LTE module. Although the linear time encoding function differs from the sinusoidal one, it still takes the raw temporal difference $\Delta t$ as input. We observe that these temporal differences are often right skewed, and TGNNs trained on the skewed input struggle with the link prediction for target node pairs that interact intermittently. By applying the logarithmic transformation to $\Delta t$ using LTE, the skewness of $\Delta t$ can be reduced, resulting in a more balanced input distribution. We have also conducted extra experiments using the linear time encoding function from [1] with LTE. Results in Table 2 below show that with LTE, the performance consistently improves.

Table 2: Test AP of TGNNs using the linear time encoding function from [1] and the enhanced version with our LTE module. Negative links are generated using the random negative sampling strategy.

[1] Chung et al. Between Linear and Sinusoidal: Rethinking the Time Encoder in Dynamic Graph Learning. TMLR

• Q2. LHA module maintains historical interactions for a target node pair that may be missed when performing temporal node message passing. Why does this approach beat RNN-like methods (e.g., TGN) that can also track very long distance interactions?

Thanks for the comment. In real-world temporal graphs, each node often interacts with a large number of other nodes, resulting in a long interaction history, or a long sequence, per node. For instance, in the UV dataset, each node interacts with over 5,000 nodes on average, forming a per-node sequence of average length longer than 5,000. However, RNNs are usually not able to track such a long sequence. Furthermore, RNN-based TGNNs still learn each node's temporal embedding based on its recent interactions. Hence, infrequent interactions are still likely to be forgotten. This forgetting problem is also empirically observed in RNN-based TGNNs, as detailed in Appendix C.5. In contrast, our LHA module explicitly encodes the historical interactions between each target node pair using dedicated historical edge embeddings and leverages these edge embeddings together with the node embeddings for the link prediction of each target node pair, thereby mitigating the forgetting problem and improving the link prediction performance.

• Q2 (cont'd). How does LHA compare to DyG2Vec [2] which also uses that past interactions for a target node pair to build temporal embeddings?

Thanks for the comment. We respectfully disagree that DyG2Vec utilizes the past interactions between a target node pair to build temporal embeddings. Instead, DyG2Vec, similar to other TGNNs such as GraphMixer and DyGFormer, learns temporal node embeddings based on each node's individual interaction history. Suppose we are to predict the link between node $u$ and node $v$. In DyG2Vec, it considers the $m$-hop neighbors (i.e., past interactions in $m$ time steps) of $u$ to learn its node embedding, together with the edge embeddings from these $m$-hop neighbors. Similarly for node $v$. However, the resulting node embeddings may not capture the interaction between $u$ and $v$, as $v$ may not be in the $m$-hop neighborhood of $u$ (and vice versa). In contrast, our LHA directly encodes the past interactions between $u$ and $v$ using dedicated historical edge embeddings, and leverages this edge embedding explicitly for the link prediction between them.

[2] Alomrani et al. DyG2Vec: Efficient Representation Learning for Dynamic Graphs. TMLR

• Q3. Does the choice of aggregation function for LHA affect performance?

Thanks for the comment. We have conducted extra experiments using different aggregation functions with varying values of $k$, where $k$ is the number of historical edge embeddings used in Equation (5) of our manuscript. The results presented in Table 3 below show that LHA is robust to the choice of aggregation functions.

Table 3: Test AP of DyGFormer on the EN and CP datasets with different $k$ values and aggregation strategies.

• Possible typo in figure 4: According to your notation $t5$ should be the oldest timestep while $t1$ is the latest timestep but the figure suggests otherwise

Thanks for pointing this out. We have updated accordingly.