FreeDyG: Frequency Enhanced Continuous-Time Dynamic Graph Model for Link Prediction

Thank you for your constructive comments and suggestions, and they are exceedingly helpful for us to improve our paper. We have carefully incorporated them in the revised paper. In the following, your comments are first stated and then followed by our point-by-point responses.

W1. From my perspective, some of the motivations regarding model designs need further verification or validation.

Response: Thank you for your comments. We give our point-by-point responses as follows:

(1) The FreeDyG model employs a sampling strategy that differs from other methods. Specifically, it involves directly sampling a fixed number of first-order neighbors from the historical interactions of the target node, prioritizing their temporal proximity. This is achieved by selecting the $L$ most recent neighbors from the historical interactions, a process with a time complexity of $O(1)$. As a result, the sampling method used in FreeDyG is more efficient than RW-based and TPP-based.

(2) We have added the pseudocode of our algorithm in Appendix D of the revised paper. Please refer to Algorithm 1 and Algorithm 2.

(3) Further experiments are carried out to demonstrate the efficiency of our filter layer. Specifically, we replace the frequency-enhanced MLP-Mixer layer with Transformer and RNN models to compare their performances, as detailed in the following table. Following reviewer Gxoa's recommendation, we employ the micro-F1 score as the evaluation metric. The results reveal that our FreeDyG model, equipped with the filter layer, delivers the highest performance across all datasets.

W2. As stated in Section 2, the authors only considered CTDG with edge addition events. It seems that the proposed method cannot handle the deletion of edges.

Response: Thank you for your comment. Our method FreeDyG currently can not handle the deletion of edges. As described in the Conclusion, we plan to expand our research to include edge deletion in future works.

W3. It seems that there are some inconsistent and unclear statements

Response: Thank you for your feedback. In the revised paper, we have addressed and corrected all inconsistencies and ambiguities. The adjustments made are as follows:

(1) In Eq. (1), we have modified the starting point of $n$ to begin from $1$.

(2) The hyperparameters $\alpha$ and $\beta$ are set to ensure that $t_{max} \times \alpha^{-(i-1) / \beta}$ approaches 0. The time encoding method used in our study is sourced from GraphMixer, as detailed in their publication available at [https://arxiv.org/pdf/2302.11636.pdf]. For more comprehensive information on this, please refer to the GraphMixer documentation. In our experiments, we have chosen the values of both $\alpha$ and $\beta$ to be 10.

(3) The parameter $\mathbf{W^{agg}}\in \mathbb{R}^{1 \times L}$ is a trainable parameter that is designed to adaptively determine the significance of various interactions. With $\mathbf{W^{agg}}$, we transform matrix $Z_*^l$ into vector $h_*^t$ with Equ. (11). Additionally, the inconsistency in the superscript $t$ arises from its omission in Section 3.1 for simplicity's sake. Those $Z_*^l$ is short for $Z_*^{l,t}$. We apologize for any confusion this may have caused.

Thank you for your constructive comments and suggestions, and they are exceedingly helpful for us to improve our paper. We have carefully incorporated them in the revised paper. In the following, your comments are first stated and then followed by our point-by-point responses.

W1: Since the proposal's effectiveness varies across datasets, it is essential to discuss the impact of Node Interaction Frequency (NIF) Encoding and the frequency-enhanced MLP-Mixer layer by investigating the characteristics of each dataset. For instance, if a certain dataset is known to exhibit periodicity, it would be reasonable to understand the benefits of the frequency-enhanced MLP-Mixer layer. Similarly, an analysis should be conducted to determine which data characteristics justified the effectiveness of NIF Encoding.

Response: Thank you for your question. The ablation study experiments depicted in Figure 3 were conducted under the random negative sampling setting, where the target node of a negative edge is sampled from the entire graph. In this setting, the negative samples are significantly easier to distinguish, and the model tends to predict future interactions between node pairs that have interacted previously. Consequently, the NIF encoding, which captures neighbor interactions, assumes a more critical role.

Furthermore, the following table presents additional experimental results from the ablation study conducted using the historical negative sampling setting. In this setting, the target node of a negative edge is sampled from the source node's historical neighbors. It is evident that the FE component holds greater significance in this setting. The reason behind this is that in this setting, the NIF encoding may introduce more false positives on negative samples, necessitating the importance of FE in capturing temporal pattern or shifting signals. For more detailed information, please refer to Figure 5 in the revised version of the paper.

W2.Some design decisions are not clear. For example, while it is crucial that $F^t_*$ represents common neighbors and their past interactions, further explanation is needed regarding the idea behind Equation 3.

Response: Thank you for your comments. In our study, we utilize $F^t_u$ to denote the historical common neighbors between node $u$ and $v$. Diverging from previous approaches that only calculate the count of common neighbors, our model defines $F^t_u$ as a 2-dimensional vector aimed at capturing the temporal patterns concealed within these common neighbors. The motivation of Equation 3 is straightforward. We use a sum pooling operation to consolidate the count information (which is mapped to a vector with dimension $d_F$ by function $f$) pertaining to common neighbors of nodes $u$ and $v$ and interaction frequency between nodes $u$ and $v$.

W3. The equation transformation involving $w_k^{(t)}$in Equation (9) is not clear. Additional clarification is necessary to understand this transformation.

Response: Thank you for your feedback. In Equation (9), we have $w_k^{(t)} = \sum_{m=1}^{N} h_m^{(t)} e^{-\frac{2 \pi i}{N} k m}$. The description has been incorporated into the revised paper.

W4: The proposed FreeDyG seems computationally expensive. However, there is no time complexity analysis. The authors are suggested to present the time complexity empirically or theoretically.

Response: Let $L$ represent the number of sampled neighbors and $d$ denote the dimension of the embdedding size. Our FreeDyG model comprises several components, each with its respective time complexity. The sampling process, which acquires the $L$ most recent neighbors, exhibits a time complexity of $O(1)$, while the encoding module operates at a time complexity of $O(Ld)$. The time complexity of the filter layer is determined by the FFT and IFFT operations, which amount to $O(L \log L)$. Additionally, the MLP-Mixer layer has a time complexity of $O(Ld)$. Consequently, the overall time complexity of FreeDyG is at most $O(L \log Ld)$. We note that the time complexity of our FreeDyG is lower than the self-attention with $O(L^2 d)$. Figure 2 in our experimental analysis displays the performance of all competing methods, along with their corresponding training time and parameter size. Notably, our FreeDyG outperforms all other approaches, achieving the highest performance while maintaining a moderate training cost.

W5:In a dynamic graph, some nodes will have more edges, but others will have fewer. Using AUC-ROC as the evaluation metrics cannot tell how good the performance of link prediction for minority nodes. I suggest reporting the Micro- and Macro-F1 scores in the link prediction tasks.

Response: Thank you for your suggestion. The results for Micro-f1 and Macro-f1 scores across all competitors are presented in Tables 7-10 in revised paper. These outcomes align with the findings from AP and AUC-ROC measurements. Notably, our model FreeDyG demonstrates superior performance compared to other baseline models in a majority of the test cases. The average ranking of FreeDyG approximates to 1 in most settings, significantly outstripping its closest competitor, DyGFormer.

Q1.Why does this work only focus on the link prediction? How is applying this work applicable to other graph mining tasks like node classifications?

Response: Thank you for your comments. In this paper, our primary focus is on the task of link prediction using the proposed method. Nonetheless, by altering the task layer and loss function settings, it can also be adapted for node classification tasks. We have performed experiments for node classification on the Wiki dataset with metric AUC-ROC (experiments on other datasets are still running). The results indicate that our method outperforms most baseline models.

Q2.For the LastFM, what is the summit of the performance when sampling more neighbor nodes? Could you please clarify the experiment details about training every baseline using the same amount of information as FreeDyG in the experiments?

Response: Thank you for your comments. We have conducted experiments with Micro-F1 metric on LastFM with $L=10,20,32,64,100,128, 160, 200$ in the following table. We can see that LastFM exhibits optimal performance when $L=100$. This requirement for a larger number of historical neighbors in LastFM is attributed to its higher average node degree, quantified as $|\mathcal{E}|/|\mathcal{V}|=653$. which is considerably higher compared to other datasets such as Reddit ($61$), Wiki ($17$), and MOOC ($57$).

Thank you for your constructive comments and suggestions, and they are exceedingly helpful for us to improve our paper. We have carefully incorporated them in the revised paper. In the following, your comments are first stated and then followed by our point-by-point responses.

W1:The motivation of delving into the frequency domain needs to be further clarified. I am wondering about the intuitions behind capturing the 'shift phenomenon hidden in the frequency domain.

Response: Thank you for your suggestion. In the field of time series analysis, examining the frequency domain has become a popular method for effectively capturing temporal signals over time. Similarly, continuous-time graph data also display temporal signals, such as the occurrence of 'shift' phenomena. These phenomena involve significant changes in the interaction patterns of nodes at specific moments. These changes in the connection patterns often result in outlier values or sudden variations in the representation vector $Z^t_*$. The basic idea of our model is straightforward: we aim for our adaptive frequency filter to capture the frequency patterns associated with temporal outliers or sudden changes.

W2:The authors claim that FreeDyG is the first work that considers the frequency information for dynamic graph embedding, which is overclaimed.

Response: Thank you for pointing out this problem. We have reorganized our statement in the revised paper as follows: Instead of the temporal domain, FreeDyG tries to address this problem by delving into the frequency domain.

W3:The authors argue that random walk based approaches are computationally expensive. However, conducting Fourier transform is also very computationally expensive. In addition, I think FreeDyG also relied on some random walk based approach to obtain the continuous-time dynamic graph from the raw graph data.

Response: Thank you for your comments.

Time complexity of Fourier transform: The time complexity of the Fast Fourier Transform (FFT) is given by $O(L \log L)$, where $L$ represents the number of sampled neighbors from historical interactions. When it comes to random walk-based methods such as CAWN, the primary computational cost lies not in the sampling process, but rather in how they utilize these walks. Specifically, after getting multiple walks, CAWN uses RNN to encode each walk as a representation and uses self-attention to aggregate the representations of multi-walks into a single vector for downstream tasks. In Figure 2, we present a comparison between our approach, FreeDyG, and the random walk-based method CAWN. It is worth noting that the training time required for CAWN on Wikipedia is double that of FreeDyG. More specifically, FreeDyG and CAWN take $67$ and $150$ seconds per training epoch, respectively. Furthermore, when applied to larger datasets such as Reddit, CAWN incurs a significantly higher time cost in comparison to FreeDyG.

Sampling strategy of FreeDyG: The FreeDyG model employs a sampling strategy that differs from random walk-based approaches. Specifically, it involves directly sampling a fixed number of first-order neighbors from the historical interactions of the target node, prioritizing their temporal proximity. This is achieved by selecting the $L$ most recent first-hop neighbors from the historical interactions, a process with a time complexity of $O(1)$.

Raw graph data: The continuous-time dynamic graph is defined as a chronological sequence of interactions between specific node pairs as explained in Section 2. For our experiments, the raw graph data is also organized in the form of an edge list, consisting of source nodes, target nodes, and timestamps. As a result, there is no need for additional operations to derive the continuous-time dynamic graph from the raw graph data.

Thank you for your constructive comments and suggestions, and they are exceedingly helpful for us to improve our paper. We have carefully incorporated them in the revised paper. In the following, your comments are first stated and then followed by our point-by-point responses.

Concerns 1: Table 3 is probably not the best way to present the hyperparameter study. Typically, one would be looking for trends as you vary the number of historical neighbors. Such trends are difficult to pick out from the table. I would suggest instead using plots with AP or AUC-ROC on one axis and on the other.*

Response: Thank you for your suggestion. In Appendix D of the revised paper, we use Figure 4 to show the trends of AP along different numbers of sampled historical first-hop neighbors.

Concerns 2: Page 7, second last paragraph: "neigh encoding"

Response: Thank you for pointing out the typo error, we have fixed it in the revised paper.

Q1: Is there a way you could inspect your trained model to identify whether any type of periodic patterns are being captured by your frequency-enhanced MLP-Mixer layer?

Response: Thank you for your comments. The frequency-enhanced MLP-Mixer layer is used to capture the periodic and shift patterns among the representation space of the historical first-hop neighbors. Different from the time series analysis problem, the periodic patterns in the hidden space of a graph may be caused by multiple interaction patterns between nodes such as repeated interactions with the same node, similar frequency of interactions, or even high-order statistic repetition.

Q2: Why is the NIF encoding more important than the frequency-based representations for improving link prediction accuracy?

Response: Thank you for your question. The ablation study experiments depicted in Figure 3 were conducted under the random negative sampling setting, where the target node of a negative edge is sampled from the entire graph. In this setting, the negative samples are significantly easier to distinguish, and the model tends to predict future interactions between node pairs that have interacted previously. Consequently, the NIF encoding, which captures neighbor interactions, assumes a more critical role.

Furthermore, the following table presents additional experimental results from the ablation study conducted using the historical negative sampling setting. In this setting, the target node of a negative edge is sampled from the source node's historical neighbors. It is evident that the FE component holds greater significance in this setting. The reason behind this is that in this setting, the NIF encoding may introduce more false positives on negative samples, necessitating the importance of FE in capturing temporal or shifting signals. For more detailed information, please refer to Figure 5 in the revised version of the paper.