Is Attention All You Need for Temporal Link Prediction? A Lightweight Alternative via Learnable Positional Encoding and MLPs

Thanks very much for your appreciation of our method’s research motivation, paper writing, and sufficient experimental results.

Your suggestions are practical and beneficial for enhancing the quality of our paper. We have organized our responses in a Q&A format below.

W1. The authors may consider improving some statements in the abstract, especially in the contribution section. Some contributions only state the process without stating the results (e.g. ‘‘verify the roles of ...’’ without saying what role they played), which is difficult to convey effective information in the abstract.

Thanks for the suggestion for highlighting our contribution. We have specified the concrete contributions in the abstract, the new texts are marked by orange color, and the updated paper is uploaded.

W2. In my understanding, dynamic graphs can be divided into two categories, namely CTDG (Continuous-Time Dynamic Graph) and DTDG (Discrete-Time Dynamic Graph). CTDG corresponds to the concept of “temporal graph”, while the graph with static snapshots mentioned in the paper is actually DTDG. The author should further investigate related work and use professional terms accurately.

First, please allow us to clarify the definition.

The definition of discrete time and continuous time dynamic graphs can be referred to the survey paper [1], where

• Continuous Time Dynamic Graph (CTDG) is represented as $((v_2, v_5), t_1)$, $((v_1, v_2), t_2)$, …, as shown in its Example 2;

• Discrete Time Dynamic Graph (DTDG) is represented as a set of $G_1$, $G_2$, …, $G_T$, where $G_t = (V_t, E_t)$ is the graph at snapshot $t$, $V_t$ is the set of nodes in $G_t$, and $E_t$ is the set of edges in $G_t$.

In this viewpoint, our method is designed for continuous time.

However, we can see a clear transformation between CTDG and DTDG: if we aggregate edges that happen at the same timestamp $t$ into a set, then it is the graph snapshot $G_t$, the example can be seen in Example 3 of the survey paper [1].

Second, we want to emphasize the reason why we bother to include “discrete” or “snapshot” in the paper.

Because the introduction and theoretical derivation on the snapshot level is much easier to be understood by the readers. Definitely, we can always use the term “a set of continuous time edges” every time when we do theoretical derivation and illustration, but it can be wordy and hurt the presentation. Since graph snapshot and relevant concepts are already existing in the community and cover the meaning, then we choose to follow them.

Reference

[1] Kazemi et al., Representation Learning for Dynamic Graphs: A Survey, JMLR 2020

W3. For this kind of dynamic graph learning based on static snapshots, will it be limited by the number of nodes? One thing that makes me curious is that the author mainly compares small-scale datasets, but also obtains good results on the large-scale datasets of TGB. So how does this learning model based on adjacency matrix adapt to large-scale datasets?

Based on the above answer, we hope we reach the consensus that the computational procedure of our SimpleTLP is categorized into the CTDG. Also, because of the existence of transition between CTDG and DTDG, and DTDG is more friendly to less notation and easy understanding, we employ the snapshot definition for the illustration.

Next, we want to give a detailed explanation of why our SimpleTLP can deal with the large-scale datasets and get good results.

SimpleTLP can be adapted to large-scale graphs due to our efficient data batching procedure (more details can be found in Appendix D.2 and E.3). In other words, our data batching procedure allows SimpleTLP to process $B$ interactions at one time, where $B$ is the batch size of training. For an arbitrary batch, our computational complexity linearly scales with the number of unique nodes in the data batch, which is at most $2B$ nodes. Then before we proceed to a new data batch, we update the positional encodings via Eq (3), which takes $\mathcal{O}(|V|)$ time, where $|V|$ is the total number of nodes in the given temporal graph. As the runtime complexity for each process linearly scales with the number of nodes in the given temporal graph, or the number of unique nodes in a data batch, SimpleTLP is able to scale up, as theoretically analyzed in Section 4 and empirically demonstrated in Appendix D.3.

Thanks very much for your appreciation of our method’s empirical performance and extensive experimental designs.

We appreciate your constructive suggestions, which helps refine our paper. Our responses are provided below in a Q&A format.

Q1. How is equation (3) designed? What is the relationship of $p^t_u$ and $\tilde{p}_u^t$ during this design for the purpose of prediction and update?

The short answer is, $p^t_u$ is positional encoding of node $u$ to be learned at time $t$, and $\tilde{p}_u^t$ is the approximated positional encoding of node $u$ for time $t$. The approximation is the prerequisite to compute the true positional encoding. Their existence is because of the problem setting of temporal link prediction, as we are not allowed to observe the interactions at time $t$ when we make the prediction for $t$.

The detailed reasoning is stated below.

• Firstly, we state the formal usage of $p^t_u$ and $\tilde{p}^t_u$. When the model makes predictions for some queried links at a certain timestamp $t$, the model is not allowed to leverage the interactions or structural information occurring at time $t$. So $\tilde{p}^t_u$, the approximated positional encoding, is constructed only based on the positional encodings of previous timestamps (timestamps before $t$) and is leveraged to help the model “approximate” the structural information occurring at time t.

• Secondly, the interaction update between them goes as follows. After processing all interactions (e.g., finished the predication) at time $t$, the model is then allowed to leverage the structural information occurring at time $t$, so we proceed to update the positional encoding that reflects the structural information including time $t$. Note that, earlier, we computed the approximated positional encoding only based on structural information at previous timestamps before $t$, $\bar{t}$ (where $\bar{t} < t$). Now that since the model’s knowledge is updated with new information occurring at time $t$, we combine this new information (structural information at time t) with the information occurring before $t$ captured by $\tilde{p}^t_u$ to obtain the positional encoding $p^t_u$.

• In summary, $\tilde{p}^t_u$ is the approximated positional encoding at time t, without “peeking” at interactions occurring at t, while $p^t_u$ is the positional encoding that also accounts for information occurring at t.

Therefore, given these reasonings, Eq (3) describes how to obtain the positional encoding $p^t_u$ AFTER the model updates its knowledge about interactions occurring at time $t$ by combining the approximated positional encoding of the node itself $\tilde{p}^t_u$ and the positional encoding of $u$’s neighboring nodes (now including those that interact with $u$ at time $t$ as the model’s knowledge is updated).

To be more specific, through the lens of the message passing architecture, we can view Eq (3) as a way of neighbor aggregation ($\hat{q}^t_u$ is sum-aggregation over $u$’s temporal neighbors) and self-update (combining with $u$’s own approximated positional encoding $\tilde{p}^t_u$), thus in this way, the model is aware of new structural information occurring at time $t$ through this “Message Passing”-based update.

Thanks very much for your appreciation, and we are quite glad to know that your concerns are addressed!

We promise to involve the above answer to our updated paper, and we are more than willing to answer any further question you may have. Thanks again!

Q3. What specific insights do you expect to gain from a deeper analysis of the parameters?

We understand your concern. As you requested, we did extra parameter analysis experiments for the parameters $L$, $\alpha_{neg}$, and $\alpha_{pe}$.

[Parameter Analysis for $L$]

We show the parameter analysis for $L$ as follows on Can. Parl. dataset below.

For the below table we can observe that our proposed SimpleTLP just relies on looking back a few historical information to make the correct information, as $L$ increases, the performance can be downgraded, and the best performance exists between 20 and 50, which discovery

• demonstrates that the near past history plays a more important role in the current decision making than the long past history,
• addresses your concern again that our proposed SimpleTLP method may needs $L$ to be quite large and effect the efficiency.

[Parameter Analysis for $\alpha_{neg}$]

We present the parameter analysis for $\alpha_{neg}$ on Can. Parl. dataset as follows:

In general, the below table shows

• our proposed method SimpleTLP is robust towards different choices of $\alpha_{neg}$,
• usually a smaller weight of negative pairs can help the model concentrate more on the positive pairs and boost the performance.

[Parameter Analysis for $\alpha_{pe}$]

We present the parameter analysis for $\alpha_{pe}$ on Enron dataset as follows:

$\alpha_{pe}$ stands for the weight of the loss function of learnable positional encoding. As shown in the following table, we can observe that

• our SimpleTLP is robust towards different choices of $\alpha_{pe}$,
• a considerable weight, e.g., 0.5, is optimal, too large or too small weight can induce suboptimal results..

Moreover, we are very interested in your suggested visualization experiments and more than willing to demonstrate it to improve our paper. Could please describe what kind of specific experimental settings you are referring to?

Q4. Can you explain the impact of the auxiliary loss on the convergence speed of your model, and how this relates to the overall efficiency of the method?

Theoretically, auxiliary loss does not always negatively affect the convergence speed of the model. As demonstrated in [1], the authors state that a suitable auxiliary loss can accelerate the convergence speed.

Empirically, we did the convergence speed comparison with SOTA baselines, as shown in Table 10 of Appendix D.3, no matter for the running time of each epoch or the number of epochs before convergence, our method is faster than those SOTA baselines.

Reference

[1] Du et al., Adapting Auxiliary Losses Using Gradient Similarity, arXiv 2020

Additional experiment of PINT as a baseline.

As requested, we incorporate PINT through empirical analysis and comparative discussion as follows.

Empirical Comparison

We present the empirical results for PINT as follows.

Currently, we have obtained the results for UCI and Enron as they are small datasets. PINT also evaluates their method on larger datasets, which are Reddit, Wikipedia, and LastFM, but PINT has not finished its empirical evaluation on these large datasets, so now we only present the results for small datasets. We will post PINT’s results when they are ready. We adopt PINT’s official implementation (via the Github link provided in the PINT paper) and use the exact hyperparameters presented in the PINT paper to reproduce their results on these datasets. Moreover, PINT and SimpleTLP use the same data split.

As shown in the above table, our SimpleTLP outperforms PINT in all experimental settings (transductive and inductive).

Comparative Discussion

PINT proposes relative positional features that count the number of temporal walks of a given length between 2 nodes. To be more specific, temporal walks are defined as follows. An $(L- 1)$ temporal walk is $W = \{(w_1, t_1), (w_2, t_2), \dots, (w_L, t_L)\}$, where $t_1 > t_2 > \dots t_L$ and $(w_{i - 1}, w_i, t_i)$ is an interaction in the give temporal graph. In summary, PINT proposes a relative positional encoding that represents pair-wise node “distance” (here the “distance” is the number of $L$-length temporal walks, assuming $L$ is given). On the other hand, our SimpleTLP learnable positional encodings (LPE) fall into the category of global positional encodings, which encode the position of the node relative to the global structure of the graph.

Thanks very much for your appreciation of our method’s interesting motivation, extensive experiments, and our paper’s clear writing.

Your suggestions are actionable, and answering them helps improve the quality of our paper. Based on your concern about the weakness, we prepare the answer in the format of Q&A below.

Thanks very much for your appreciation of our method’s interesting motivation, extensive experiments, and our paper’s clear writing.

Your suggestions are actionable, and answering them helps improve the quality of our paper. Based on your concern about the weakness, we prepare the answer in the format of Q&A below.

Q1. How does your approach build upon or differ from existing methods for learnable positional encoding in static graphs?

To the best of knowledge, the only work for learnable positional encoding is LSPE [1], which is designed for static graph neural network and graph classification tasks.

In short, different from [1], our learnable positional encoding first attempts to graph data and also accounts for its temporal dependencies via Eq (1) and Eq (2).

Therefore, next we would provide two directions of explanations for answering "What makes static graph positional encoding insufficient for dynamic graphs?" and "How does our proposed method differ from those used in static graphs?"

1. The insufficiency of static methods

On the one hand, if we apply positional encoding methods on static graphs (Laplacian, Random Walk Positional Encoding, etc.), everytime the model updates its knowledge, i.e., receive interactions of new timestamp, static methods would have to re-compute the positional encoding (based on Laplacian, Random Walk, etc.) which is a computational burden.

On the other hand, applying static methods to the temporal setting relies on taking the time individually, for the task that requires the temporal patterns to be encoded, static methods can produce suboptimal results. Just take the temporal link prediction task, the prediction (or the label) indicating whether two entities would be connected or not depends on a series of historical behavior, where static methods are usually not capable to capture that, as shown in Table 1 of [2], Table 1 and Table 2 of [3], and Table 2 of [4].

2. Difference between our method and static methods

Motivated by point 1, we propose an efficient method to learn the positional encoding for future timestamps, without re-compute the positional encoding everytime the model’s knowledge is updated, avoiding the computational burden. To be more specific, LSPE proposes learnable positional encoding (LPE) as follows.

On the one hand, LSPE initializes their LPE with well-defined positional encodings such as Laplacian, or Random Walk Positional Encoding, then obtains the final LPE via multiple layers of Message Passing. Their LPE of a node $u$ at the $(l + 1)-$th Message Passing layer is computed by aggregating the concatenation of (1) $u$’s adjacent edge encodings at $l-$th Message Passing layer and (2) LPEs (from $l-$th Message Passing layer) of $u$’s neighbors.

On the other hand, our proposed LPEs only execute 1 round of aggregating the approximated positional encodings of neighboring nodes. Moreover, LSPE proposed the loss function for their LPE is designed to enforce the LPEs to have a centered and unit norm with zero mean, and better approximate the Laplacian eigenvectors. On the other hand, our loss function for our proposed LPE is designed to reflect the nature of node positional encodings (i.e., the more closer 2 nodes are, the more similar their positional encodings are) by minimizing the 2-norm LPEs difference of positive samples, and maximizing the 2-norm LPEs difference of negative samples.

Reference

[1] Dwivedi et al., Graph Neural Networks with Learnable Structural and Positional Representations, ICLR 2022

[2] Trivedi et al., DyRep: Learning Representations over Dynamic Graphs, ICLR 2019

[3] Xu et al., Inductive Representation Learning on Temporal Graphs, ICLR 2020

[4] Wang et al., TCL: Transformer-based Dynamic Graph Modelling via Contrastive Learning, arXiv 2021

Thank you very much for the author's rebuttal. You have addressed most of the concerns, but I still have some questions regarding Q2.

1. You generate positional encoding by selecting $L$ different historical event timestamps. However, in dynamic graphs, a large number of interactions can occur simultaneously. Additionally, I noticed that the values of L you chose in Q3 are relatively large (even up to 100). Does LSPE maintain high efficiency and performance in dynamic graphs with a large number of interactions occurring at the same timestamps?
2. LSPE pre-computes the positional encoding, making the model to be not end-to-end. However, the authors mentioned that their method is "learnable." How is this part optimized, and what is the objective?
3. Default model parameters should be included in the section of model configuration.

After re-reading your manuscript, I noticed that most of the rebuttal content and experimental results (not limited to the response to me) have not been incorporated into the paper. I believe it would be great to see this information included in your revised paper.

Dear Reviewer XPj9,

We sincerely thank you again for your appreciation of our last-round response answers.

After gaining your appreciation and confirmation, we had added the new experiments with detailed descriptions to the paper, marked by the orange color. The new paper had been uploaded already.

Since the due for uploading the pdf is close to the end in a few hours, i.e., 11:59 PM AOE Time 11/27, may we gently and kindly remind you to have a look at our updates?

If there are any updates you suggest, we can make them before the upload due date.

Thanks very much!

Authors

Dear Reviewer XPj9,

As requested, the new baseline PINT’s empirical results on other larger datasets are ready and we report them in the following table.

As shown in the Table, the observation is consistent with our previous discovery, and our SimpleTLP outperforms PINT. As always, we promise to add them to our paper.

Dear Reviewer XPj9,

Thanks very much for your time and helpful review!

As requested, we have finished additional theoretical analysis and empirical experiments, and we updated the pdf file with colored parts. We are quite glad to learn that you acknowledge that most of your concerns have been addressed already.

Moreover, we appreciate that you further propose three sub-questions for Q2 in the first round. Regarding that, we further carefully prepared the extended answer from theoretical and empirical perspectives.

We enjoyed exchanging ideas with you very much. Since the discussion period will close in a few hours, we would like to gently ask if you need any further discussions for our second-around answers for your re-evaluation. We would wholeheartedly answer any of them until the last minute.

Thanks very much!

Authors

Thanks very much for your review and appreciation of our method’s theoretical soundness, neural architecture design, and solid experiments!

Addressing your concerns improved the quality of our paper, and we prepared the answer in the Q&A format below.

W1. The idea of positional encoding and discrete Fourier transform is not new in the field of dynamic graph learning. This paper applies DFT only to the positional embeddings {$\{\mathbf{p}\_{u}^{t}\}$}, rather than to the final representation {$\{\mathbf{h}\_{u}^{t}\}$}. I am curious about the benefits of doing so.

First of all, positional encoding is a necessary prerequisite for the self-attention mechanism, which provides the position information in the sequence that will be attended. Instead of setting the positional encoding as hand-crafted and fixed [1], our method and efforts focus on (1) how to propose a learnable positional encoding that is expected to be more expressive than pre-defined, hand-crafted, and fixed positional encodings, (2) and how to extend it to the time-evolving setting, such that the positional encoding can convey temporal information and be robust across timestamps. To the best of our knowledge, these topics have not been studied by previous works.

Second, Discrete Fourier Transform (DFT) is a classic concept. However, to the best of our knowledge, the only previous work that applies DFT in dynamic graph representation learning is FreeDyG [1], and it has been discussed in detail and set as the SOTA baseline for 13 classic datasets and with 8 other algorithms in both transductive and inductive settings using 3 different sampling strategies, where our SimpleTLP achieves the best performance consistently.

The reason we can achieve the above performance is that we are not just simply using DFT, but we adapt it in a principled way to the dynamic graph setting, as shown in Eqs (1 - 2). To be more specific, our learnable positional encodings are constructed based on the reasoning that the evolving graph’s structure is associated with temporal dependencies. On the other hand, node / edge raw features are hand-crafted or domain-specific injected features, so these features are not necessarily related to temporal dependencies. Moreover, some datasets do not support node / edge features. Therefore, we only apply DFT on positional-related information so that we can effectively capture the aforementioned temporal dependencies

Reference

[1] Dwivedi et al., A Generalization of Transformer Networks to Graphs, DLG-AAAI 2021.

W2. In the viewpoint of graph signal processing, the eigenvectors of graph Laplacian matrix represents the basis of low-frequency signals on the graph [1]. When the graph structures evolve over time, the basis would probably change, then it is not clear to me what kind of information the filter in Eq. (1) can learn. Please remind that the high-frequency noise in for example $\mathcal{G}^{t_{i}}$ might correspond to low-frequency signal in another snapshot $\mathcal{G}^{t}$ [2].

To the best of our knowledge, not all eigenvalues of the graph Laplacian correspond to low-frequency signals on the graph, but actually small eigenvalues correspond to low-frequencies while larger eigenvalues correspond to higher frequencies.

We understand your concerns about whether learnable positional encoding can fit the time-evolving setting well. Therefore, we give the following in-depth explanation.

Theoretically, we would like to provide more elaborations on the significance of our learnable filter in Eq (1). We first apply DFT on $u$’s sequence of approximated positional encodings {$p^{t’}_u$} (where $t'_1 \leq t' \leq t'_L$), and the the learnable filter filters out high-frequency noise across dimensions of the input approximate positional encodings, and finally the Inverse DFT transformed the filtered positional encodings back to the original domain. It is noteworthy that we are apply DFT on the sequence of approximated positional encodings of the node itself (i.e, the sequence consists of previous approximated positional encodings of the same node), instead of basis, formed by the positional encodings of every node, of the whole graph.

Empirically, given (1) 13 classic dynamic graph datasets and with 10 algorithms in both transductive and inductive settings using 3 different sampling strategies and (2) the open worldwide large-scale dynamic graph benchmark, our method shows superior performance.

W3. It seems that p_u^t in Eq.(3) encodes the spatial positional information, h_{u,N}^t encodes the node features, and h_{u,E}^t encodes the edge features and the time intervals between recent interactions. I am not sure whether h_{u,N}^t is capable of learning sequential patterns in the neighborhood. This is very important for personalized recommendation. To be specific, the sequence order of historical items (i.e., 1-hop neighboring nodes) for a target user (i.e., query node) will reflect her/his future behaviors.

$h^t_{u, N}$ is capable of capturing sequential patterns.

In the context of personalized recommendation, if a node $u$ interacts with $v$ many times (for example, a user purchases an item many times) then the raw node feature of $v$ is emphasized in $h^t_{u, N}$.

Similarly, $u$’s node feature is also emphasized in $h^t_{v, N}$, making $h^t_{u, N}$ and $h^t_{v, N}$ closer in the embedding space.

W4. Theorem 1 states that the positional embeddings would similar to each other when temporal graph is slowly changing, then one raising concern is whether DFT is necessary. Personally, I believe that it would be more interesting to see that LPE has the ability to learn abrupt changes.

In brief, DFT is necessary for the real-world temporal link prediction setting and is the key point for our model achieving the comprehensive outperformance, as shown in LPE ablation study in Appendix D.4. To further address your concern, we would like to go through Theorem 1 intuitively for you.

In short, it shows that when the temporal graph is slowly evolving with respect to time, the learned positional encoding at previous timestamp can well approximate the next close future timestamp’s positional encodings.

Theoretically, the significance of Theorem 1 is to demonstrate the effectiveness of our proposed LPEs in the inductive setting, where future graph structural information is hard to observe, such that the “slowly changing” assumption for the coming snapshots is needed for this theoretical derivation. Moreover, defining a degree of change over temporal snapshots is an interesting but largely open question, which may involve the random matrix theory and relevant knowledge [1], and so far no clear definition, to the best of our knowledge. Therefore, assuming the temporal smoothness [1], i.e., next snapshot will not change dramatically from the previous snapshot, is a greedy quick-win solution for now, and we are more than happy to dive in this topic for our future research direction.

Empirically, Theorem 1 does not necessarily suggest that we do not need to update the positional encodings. Actually, we update the positional encoding to avoid the possible unpredictable changes, the detailed procedures are as we answered in Q3, and the comprehensively outperformance demonstrates our effectiveness.

Reference

[1] Chi et al., Evolutionary Spectral Clustering by Incorporating Temporal Smoothness, KDD 2007

---

[Minor comments are also addressed below]

M1. It would be better to recall the definitions of $f_{T}$ and $\mathbf{e}$ in line 247.

$f_T$ denotes the time encoder and $e$ denotes the edge feature. The explanation is added to the new paper and marked by orange color, and the updated paper is uploaded.

M2. It seems that the computational complexity of eigenvalue-decomposition is not mentioned in complexity analysis. As far as I know, it is quite expensive to achieve orthogonalized (approximate) eigenvectors. This would largely limit the application of the proposed model. (I read D.6 which has addressed part of this issue.)

Thanks for reading our Appendix D.6 for the robust performance of our SimpleTLP across different positional encodings.

No matter in the main body of the paper or Appendix D.6, the positional encodings are just initial inputs to trigger our method as stated in lines 028, 077, and 216. This computation is pre-computed and does not need to be recomputed in our method as time goes by. On the contrary, this is one of contributions to learn and update the positional encodings in the time-evolving setting.

Since it is out of the scope of the main story of the proposed SimpleTLP and can be replaced with other positional encodings with the similar results, that's why we view it as a dispensable condition of executing SimpleTLP and did not include into the time complexity analysis of our SimpleTLP.

In the revised paper, let us recall Eq. (4) as follows:

$h_u^t = s_u^t + MEAN( s_0, \dots, s_k )$

where $s_u^t$ denotes the user feature, and $s_i$ denotes the item feature. It seems to me that $h_u^t$ is invariant to the order of item sequence $[s_0,\dots, s_k]$. Even if applying time encoding $t_0$ to $s_0$ (the user interacts with item $s_0$ at time $t_0$), it is not clear to me what kind of sequential patterns $h_u^t$ is able to learn from the data $[s_0,\dots, s_k]$, since only Mean-Pooling is used.

(1) Why the time encoding is important and what information they encode

(2) Why we choose sum pooling over time encoding

First apologize for the late response, and appreciate for the authors' responses.

Let us take a simple example to understand Q2: $L^{t_i}=[v_0, \dots, v_n]^T \textrm{diag}(\lambda_0, \dots, \lambda_n) [v_0, \dots, v_n]$ represents the Laplacian matrix at time $t_i$ where $\lambda_0\le\dots\le\lambda_n$, where $L^{t_j}=[v_n, \dots, v_0]^T \textrm{diag}(\lambda_0', \dots, \lambda_n') [v_n, \dots, v_0]$ signifies the Laplacian matrix at time $t_j$ where $\lambda_0'\le\dots\le\lambda_n'$. In this case, a graph signal $\mu = v_0$ corresponds to the low-frequency signal on graph $G^{t_i}$, but it corresponds to the high-frequency signal on graph $G^{t_j}$.

The example above explains that the informative representation $\mu$ on a graph snapshot might be noisy signal in another graph snapshot. From this view of point, the basis of low-frequency signals will be evolving, what is the accurate definition of low-frequency signals in the evolving graph?

I highly recommend the authors to make a further study about what DFT can essentially learn from the positional embeddings on evolving graphs. I deeply believe that this can largely help the readers to understand how the proposed positional encoding works theoretically.

(3) Why the sum pooling did not hurt the performance

• Theoretically, the reason that we can utilize this design is that {$s^{t’}\_{u’}$} is already constrained in a time interval $[t- t\_{gap}, t]$.

  • Since the time interval is small enough (i.e., all are recent interactions), any interaction ($u, u’, t’$) would tend to have the equal chance of affecting $u$ at time $t$.
  • As shown in Table 22 and Table 6, the ratio of $t\_{gap}$ / (number of unique timestamps) for all datasets is at most $0.167$. The interval $[t- t\_{gap}, t]$ would contains at most $t\_{gap}$ distinct timestamps (since the granularity in Table 6 indicates that timestamps are integers). Therefore, with such a small ratio above, the interval $[t - t\_{gap}, t]$ contains timestamps that are very close to $t$.

• Empirically, the aggregation manner is model-agnostic, which means we can use other pooling functions. Therefore, we prepared an additional pooling function, i.e., time weighted pooling function, to prove our theoretical guess.

  • Time weighted pooling function is sensitive to the temporal order, i.e., the more recent timestamp will occupy more weights during the aggregation. In this way, if the order changes then the output will be different. It has the following mathematical equation.

  • Suppose we have $M$ distinct timestamps in node $u$’s interactions during the time interval $[t - t_{gap}, t]$ and let’s denote them as $t_1, \dots t_M$ (where $t_1 < \dots < t_M$), then the weight for the node that interacts with $u$ at time $t_i$ would be $e^{-(t - t_i)} / \sum_{j} e^{-(t - t_j)}$. In other words, we obtain weights by applying softmax on $-(t - t_1), \dots, -(t - t_M)$.

  • In this way, Eq. 4 would be $h^t\_{u, N} = s^t\_u + \sum\_{(u, u’, t’\_j)} \alpha\_{t’_j} s^{t’_j}\_{u’}$, where $(u, u’, t’\_j)$ are interactions involving $u$ during the time interval $[t - t\_{gap}, t]$ and $\alpha\_{t’_j} = e^{-(t - t’\_j)} / \sum\_{j = 1}^M e^{-(t - t\_j)}$

  • With the above new question replacing Eq. 4, the experiments are shown in the following table, where we can see that sum pooling can achieve a very competitive result, which aligns our theoretical design: in a short time window, the equal contribution (i.e., sum pooling) can be effective and efficient. Moreover, handicraft design for the aggregation weight is not alway efficient and suitable for all cases.

---

Table. Performance of Different Pooling Function on Eq. 4.

Dear Reviewer Ysht,

We want to express our sincere thanks for your time and review!

We enjoyed the discussion with you, and we are very grateful for your appreciation of our first-round answer addressing most of your concern.

Beyond that, for your two further questions, we took them seriously and prepared the detailed theoretical analysis and empirical demonstration.

Since the author-reviewer discussion will end in a couple of hours, we kindly remind you and gently ask if you are satisfied with the second-round answer or need more discussions for your re-evaluation.

We are more than willing to try our best to answer any further questions until the last minute.

Thanks very much!

Authors