Learnable Spatial-Temporal Positional Encoding for Link Prediction

Thanks very much for your review!

We are excited to learn your appreciation of our model's design, effectiveness and efficiency, and paper's writing.

Your suggestions are actionable and helpful.

First of all, we correct the typo in Eq (11) and promise to update it in our camera-ready version.

Then, we would like to further discuss your concern in the experimental setting.

[Data Source]

The datasets used in our paper, according to [2], is firstly collected by [1].

However, as a library, [2] provides detailed all dataset processing and baseline implementation, https://github.com/yule-BUAA/DyGLib, and we used all the datasets from [2].

[Implemtation]

We strictly followed the implementation of [2] and reported the performance.

For more clarification, we follow the training and evaluation settings of [2] as follows.

• Specifically, during training, we compute the loss function and perform back propagation for the model only using randomly sampled negative links.
• Then, with this trained model, we test the model on random, historical, and inductive negative edges.
• The corresponding configurations are listed in Appendix I of the paper.

[Proof from Other Sources]

Beyond 13 classic datasets in [2], we also tested our method on the open-source worldwide large-scale benchmark leaderboard, TGB [3] (https://tgb.complexdatalab.com/docs/leader_linkprop/), which also provides the standard dataset split and training paradigm.

In TGB, our method also achieves a very competitive performance in temporal link prediction tasks, as shown in Table 2 of the paper.

[Code Release]

We promise to release our code upon publication.

---

Reference

[1]: Poursafaei, Farimah, et al. "Towards better evaluation for dynamic link prediction." Advances in Neural Information Processing Systems (2022)

[2]: Yu, Le, et al. "Towards better dynamic graph learning: New architecture and unified library." Advances in Neural Information Processing Systems (2023)

[3]: Gastinger, J., Huang, S., Galkin, M., Loghmani, E., Parviz, A., Poursafaei, F., Danovitch, J., Rossi, E., Koutis, I., Stuckenschmidt, H., Rabbany, R., and Rabusseau, G. TGB 2.0: A benchmark for learning on temporal knowledge graphs and heterogeneous graphs, Advances in Neural Information Processing Systems (2024)

Thanks for your appreciation of our method’s soundness and experimental design! Addressing your concerns improved the quality of our paper, and we prepared the answer below.

How learnable positional encodings work in dynamic environment.

Due to the length limit of response, we sincerely invite you to check our first answer in U1pJ

W1: First paragraph of section 3.1 is a large run-on sentence, use LLM to refine.

Thanks, we will.

Q1: What is the spectrum of filtered noise in your experience?

We would like to elaborate on what kind of information our learnable filter (used in Eq (1)) learns.

Theoretically, we first apply DFT on $u$’s sequence of learned positional encodings at previous timestamps {$\mathbf{p}^{t’}_u$}, then the learnable filter filters out high-frequency noise across dimensions of the learned positional encodings in the spectral domain, and finally, the Inverse DFT transformed the filtered positional encodings back to the original domain.

Practically, the filtered noises are those that cannot contribute to link prediction decisions.

Q2: By using the DFT to model ...

First, to our understanding, the sequence is not necessarily wave-like to be decomposed by DFT, so we do not constrain our positional encoding to follow any wave-like dynamics. In addition, we did not consider applying cosine or sine bases, since DFT’s bases already contain cosine and sine components.

Q3: How is p0 computed for a new vertex?

If a new vertex emerges, we first initialize this vertex’s positional encoding to a zero-valued vector, then proceed with the model's computations to make link predictions involving this vertex.

Q4: How does the DFT relate to ...

We clarify the difference between DFT and traditional graph fourier transform, then elaborate on why employing DFT is more suitable for the temporal link prediction problem as follows.

DFT is leveraged for processing time-series-like data, while graph fourier transform analyzes the signal associated with nodes of a graph. Intuitively, the signals in time-series are defined along a timeline, i.e., each timestamp on the timeline produces a signal, while graph fourier transform processes signals defined on nodes of a graph, i.e., each node is associated with a signal, for example, each node of the graph has a node feature vector.

• In our framework, we are trying to “approximate” a node $u$’s positional encoding at time $t$ based on its positional encodings in previous $L$ most recent distinct timestamps, $\{\mathbf{p}\_u^{t’\_j}\}\_{j = 1}^L (t’\_j < t, \forall j)$, so through the lens of DFT, we can consider $\{\mathbf{p}\_u^{t’\_j}\}\_{j = 1}^L$ as a sequence of signals defined on a timeline, where each timestamp $t’\_j$ produces the signal $\mathbf{p}\_{u}^{t’\_j}$.
• Graph fourier transform (GFT) acts as a convolution on the graph, i.e., GFT computes a node’s representation based on other nodes’ information and GFT is defined for static graphs, while we only want to obtain a node’s positional information based on its positional information at previous timestamps, so we think that DFT is a better fit for our goal.
• Due to the difference in the definition and setting between DFT (for sequences, temporal data) and GFT (for static graphs), we do not expect the filter of L-STEP to be similar to the filters learned by traditional MPNNs.

In short, we aim to analyze the temporal dependencies in the sequence of node $u$’s positional encodings at different timestamps, so we employ DFT, which is a better fit for sequences and time-series-like data, while GFT operates convolution on static graphs.

Q5: How did you implement the complex-valued gradient ...

In our implementation, we first initialize $\mathbf{W}\_{filter}$ using nn.Linear() module of PyTorch library and then convert the parameter to torch.complex64 data type, i.e., turning $\mathbf{W}\_{filter}$ into a complex-valued tensor. Now, we present our implementation to obtain Eq (1) as follows. Suppose batch_pe is $\{\mathbf{p}\_{u}^{t’\_j}\}\_{j = 1}^L$ and filter is $\mathbf{W}\_{filter}$.

The pseudocode for implementing Eq (1) could be described as follows:

1. filter = nn.Linear(d_P, L, bias = False).to(torch.complex64) // initialization of W_{filter}

For epoch in range(num_epochs): // model training phase
   2. batch_pe = batch_pe.to(torch.complex64) // convert batch_pe to complex-valued tensor        
   3. batch_pe = fft.fftn(batch_pe, dim = 1) // apply FFT transformation on batch_pe
   4. batch_pe = filter.weight.unsqueeze(0) * batch_pe 
   5. batch_pe = fft.ifftn(batch_pe, dim = 1) // apply inverse FFT
   6. batch_pe = batch_pe.to(torch.float32) // convert back to float32 data type

Here, the 4th line of the pseudo code represents $\mathbf{W}\_{filter} \odot \mathcal(\{\mathbf{p}\_{u}^{t’\_j}\}\_{j = 1}^L)$, and the 5th line is equivalent to applying inverse DFT. Finally, we convert batch_pe back to real-valued tensors.

Thanks very much for your review! We are excited to learn your appreciation of our extensive experiments and corresponding outperformance.

Your suggestions are quite actionable, and we seriously prepared the answer in Q&A format below.

W1: The low changing aspect needs to be tested.

First, the outperformance of our method across all 15 real-world datasets has proven our theoretical design is valid to some extent.

Of course, we understand your concern, and prepared the illustration of the slowly changing pattern in the real-world graphs below, by taking UNVote dataset as an instance. The assumption is further proved, and we promise to add this new content to our camera-ready version.

[Positional Encoding Patterns with Time]

• In the 1st plot of UNvote, the x-axis represents timestamps, and y-axis represents the distance between each consecutive pair of positional encoding, i.e, $\mathbf{p}^t$ and $\mathbf{p}^{t + 1}, \forall t$. As $\mathbf{p} \in \mathbb{R}^{|V| \times d_P}$, which is a matrix and $i$-th row is the positional encoding of node $i$
  • We compute the distance between $\mathbf{p}^t, \mathbf{p}^{t + 1}$ by first computing the Euclidean distance between $\mathbf{p}\_u^t$ and $\mathbf{p}^{t + 1}\_u$ and then let the mean of Euclidean distance of positional encoding overall all nodes, i.e, $\frac{1}{|V|} \sum_{u \in V} d(\mathbf{p}\_u^{t}, \mathbf{p}\_u^{t + 1})$, be the distance between $\mathbf{p}^t$ and $\mathbf{p}^{t + 1}$.
  • We discover the distance between each consecutive pair of positional encoding, $\mathbf{p}^{t}$ and $\mathbf{p}^{t + 1}$ is consistently small across all timestamps.
• In the 2nd plot, we illustrate the distance between our learned positional encoding and the true positional encoding for each graph snapshot
  • Overall, the distance between our learned positional encoding and the true positional encoding of each snapshot is consistently small across all timestamps.

[Theoritical Explaination]

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 quick-win solution for the theoretical derivation, and we are more than happy to dive in this topic for our future research direction.

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

W2: Available code.

We promise to publish our code upon the paper’s publication. Also, we are preparing an anonymous link, so we can share the implementation shortly (before the deadline for final response).

W3: Hyperparameter sensitivity.

Based on our parameter analysis, our model is comparatively robust to bad choices, i.e., we experience drops in performance while varying the hyperparameter but the drops are not significant. For more details and intuition for choosing the hyperparameter, please refer to Appendix H.5.

Q1: Why are FreeDyG results missing in table 11?

Original FreeDyG did not run on UNTrade dataset. We follow FreeDyG’s official implementation, but the corresponding performance is around 0.500. We will add this explanation to our camera-ready version.

Comment 1: The main article does not contain dataset descriptions and most of the reported results.

Due to page limit, the description is in Appendix G. Results of other experimental settings (historical and inductive negative sampling), ablation study, and parameter analysis are in Appendix H.

Comment 2: L-step results are bolded in table 2 right panel but these are not the best results.

Table 2 is ranked from top to bottom with a ranking index; we bold our method for just highlighting its position.

Suggestion: I would like to see an HTGN comparison to see how it compares to hyperbolic methods, but there are two recent and A+ articles. They seem enough.

We understand, and we are adapting HTGN to this paper's setting. If finished early, we will post HTGN’s results before the final response deadline. If not, we will add it to our camera-ready version.