SALoM: Structure Aware Temporal Graph Networks with Long-Short Memory Updater

We are glad that the reviewer appreciates our work as a solid and effective contribution. Thank you for new dataset resource that we can further extend our study on. We have carefully revised the manuscript according to your constructive suggestions. Below, we address the main points raised in the review.

W1: New datasets

Thank you for raising this question. But due to time constraints and huge GPU memory demands, and with access limited to only two NVIDIA RTX 4090 GPUs, we only tested our model on a subset of datasets from TGB-seq to evaluate MRR performance. The results are presented below. We observe that SALoM outperforms all baselines on non-bipartite datasets, especially by a large scale on Flickr. For bipartite datasets, SALoM outperforms all universal baselines, however its performance is slightly inferior to the specially tailored baseline.

Thank you again for the new dataset resource, we will further study into them and add evaluations on them in the next version.

W2: Potential flaw of information leakage

We sincerely appreciate you identifying this important issue regarding test information leakage, which indeed affects our method and comparable memory-based baselines (TGN, DyRep, JODIE). To maintain fairness in our current comparisons while addressing this concern, we will: (1) retain the existing evaluation setup for this version to ensure consistent benchmarking, and (2) implement crucial fixes in our codebase to properly batch same-timestamp edges during testing, with updated results to be included in our next manuscript version.

Q1: LSMU adopted to other memory-based models

Thank you for your question, we will elaborate below.

Since LSMU is designed for the memory update process, it serves as a universal memory updater for all memory-based methods. Notably, LSMU was initially developed on TGN; therefore can allow straightforward adaptation to other memory-based methods for accuracy improvements. We also extended our experiments on TGN with the default setting and only alteration of the memory updater to support this view as follows.

Thank you for your insightful review. Since receiving your feedback, we have been actively addressing the data leakage issue you raised and are pleased to share our progress.

First, regarding memory-based methods (the predominant approach for modeling C-TDGs[1,2,3]), while existing literature overlooks data leakage's impact on final performance, we have nevertheless prioritized resolving this issue. Notably, our proposed SALoM framework maintains its state-of-the-art performance, demonstrating significant improvements over all existing memory-based methods across all benchmark datasets, including the new Flickr, YouTube, and ML-20M datasets you kindly provided [4].

Second, we have worked diligently since the rebuttal stage to eliminate data leakage in memory-based methods through a simple time-aware dual memory management. Specifically, we maintain two separate memories: one to store the final state of the previous timestamp and another to continuously update within the same timestamp. During inference, we strictly select the memory corresponding to timestamps earlier than the current edge to form node representations, while using the second memory to maintain ongoing updates. When inference proceeds to the next timestamp, the accumulated updates are synchronized to the first memory, ensuring updates are applied without information leakage.

The coding adjustments are now complete, and we will share updated results shortly.

[1] GRAVINA, Alessio, et al. Long range propagation on continuous-time dynamic graphs. arXiv preprint arXiv:2406.02740, 2024.

[2] SU, Junwei; ZOU, Difan; WU, Chuan. Pres: Toward scalable memory-based dynamic graph neural networks. arXiv preprint arXiv:2402.04284, 2024.

[3] DENG, Gangda, et al. TASER: Temporal adaptive sampling for fast and accurate dynamic graph representation learning. In: 2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2024. p. 926-937.

[4] YI, Lu, et al. Tgb-seq benchmark: Challenging temporal gnns with complex sequential dynamics. arXiv preprint arXiv:2502.02975, 2025.

Thank you for your feedback, but there seems to be some misunderstanding. We would like to clarify that our approach does not modify TGN’s core memory update mechanism, as the previously described secondary memory still processes ongoing updates using the last interaction in the last batch, exactly as in the original TGN. However, to prevent potential information leakage (since the last interaction in the last batch may occur exactly at the prediction time $t$), we avoid using this updated memory for computing node embeddings. Instead, we introduce a separate memory component that stores only the final state from the previous timestamp, ensuring temporal consistency in predictions.

To avoid misunderstanding, we give a concrete example. Consider that we maintain two memory units, ensuring that the timestamps $t_1$ and $t_2$ of the two memory units satisfy the condition $t_1 < t_2$. In this context, $t_1$ represents the data information that can be observed in real scenarios, while $t_2$ stores the memory unit corresponding to the current prediction time frame. This setup allows us to effectively update $t_1$ for future predictions.

If for the subsequent event to be predicted $(u, v, t_3)$, we have $t_1 < t_3 = t_2$, then we will use the state recorded at $t_1$ to calculate the memory updater and merge the last event into the memory unit at $t_2$. If $t_1 < t_2 < t_3$, we will use the memory at $t_2$ for model calculations. In this case, the timestamps of subsequent events will be greater than or equal to $t_3$, allowing the memory recorded at $t_2$ to replace that of $t_1$.

This ensures that there is always a memory unit state that is strictly less than the current timestamp and corresponds to the last interaction involved in the calculation. This approach not only avoids the common data leakage issues of traditional TGN but also eliminates the memory and computational overhead of searching for updated states in historical memory records.

As space constraints, we will share our experimental results in the comment below.

We sincerely appreciate the reviewer's recognition of our work as a solid contribution and their valuable suggestions for potential extensions. Below we respond to the main points raised in the review.

W1&Q1: LSMU overhead

We appreciate the insightful feedback. We have extended our experiments and show the results below. While LSMU does incur higher computational overhead than GRU due to its enhanced capabilities, it maintains reasonable efficiency overall. The GPU memory requirement doubles due to its two-expert selection, but we argue this trade-off is justified by the substantial accuracy improvements achieved.

Table 1: Training time and GPU memory comparison of GPU and LSMU

W2: Equation clarity

Sorry for the confusion. We appreciate the feedback and will add illustrative plots in the next version to enhance clarity.

Equation 1 defines Neural ODE, where the algorithm does not directly model the mapping of the independent variables to the dependent variables but instead models the derivative of the corresponding function. Also, this approach computes gradients by integrating the second-order derivatives over the relevant time interval, eliminating the need for discrete chain-rule multiplications and thereby avoiding the vanishing gradient problem. Equation 2 specifies the closed-form solution of the Liquid Time-Constant (LTC) network employed in our method. Building upon the original framework, and also introducing a gating-like mechanism and utilize a trainable network to compute the time-dependent damping coefficient, capturing the temporal influence on events.

The objective of the Information Bottleneck (IB) is to generate an intermediate representation of the original representation that maximizes information correlating with the training target while minimizing noise in the original representation. Here, correlation is characterized by mutual information. However, as mutual information is difficult to compute in practice, we optimize an upper bound of the target function instead. By employing variational approximation, we scale the target function to derive the mathematical form of its upper bound. This upper bound can then be transformed into a form combining Binary Cross-Entropy (BCE) loss and KL divergence, with the detailed derivation provided in Appendix C. Consequently, when aggregating multiple features using the IB approach, not only is feature fusion achieved, but noise reduction is also inherently accomplished.

W3: Application examples

We appreciate the suggestion to include real-world applications. While time constraints prevented us from implementing a fast-deployable case study in this version (as is common in similar works), we recognize their importance and will explore concrete application scenarios (such as policy change tracking) in future work to better highlight the practical relevance of our approach.

W4: Differences from other MoE-based GNNs

Thanks for your insightful advice. Unlike typical MoE-GNNs that apply mixture-of-experts during node aggregation, our approach uniquely integrates MoE exclusively within the LSMU to explicitly separate long-term and short-term dependency learning. This targeted implementation allows MoE to serve distinct functional roles based on contextual requirements, making our architecture both more specialized and adaptable than conventional implementations.

Q2: Hash collisions

We appreciate the insightful question about hash collisions. While collisions can theoretically impact accuracy, SALoM's dual hash table design (long-term and short-term) effectively mitigates this by simultaneously capturing behavior patterns at different timescales. Importantly, collisions actually provide a beneficial side effect by facilitating timely updates and replacement of outdated information in the hash tables.

Q3: Edge feature dynamics

Thanks for your insightful advice. The dynamic graph task inherently involves continuously changing edges, the edges with dynamics edge will be viewed as a new edge despite of the same source and destination nodes. Consequently, SALoM is naturally designed to effectively handle these changing edge features.

We sincerely appreciate the reviewer's positive feedback on our model design and experimental rigor, as well as their constructive comments that helped improve our paper. Below we respond to the main points raised.

W0：Individual motivations:

We apologize for any confusion and now provide analytical and experimental motivation for each SALoM component:

a) ODE-based memory updater for long-term temporal correlation:

Traditional sequential methods (RNNs/GRUs) treat dynamic graphs as discrete events, struggling with temporal continuity and long-term dependencies due to gradient issues. In contrast, ODE-based methods preserve continuity and avoid gradient issues through second-order derivative integration, demonstrating superior long-term dependency capture with minimal information loss (Table 1, [1]). This experiment is designed to predict the label(-1/1) of the first node with node embedding propagated through a linear graph of length(n). However, our ablation studies (Fig. 2) show that over-emphasizing long-term dependencies can cause over-globalization. We therefore propose LSMU, an MoE-based approach that dynamically balances long/short-term dependencies, adaptively selecting the optimal processing.

Table 1: Accuracy under different numbers of sampling neighbors

[1]GRAVINA, Alessio, et al. Long range propagation on continuous-time dynamic graphs. arXiv preprint arXiv:2406.02740, 2024.

b) GRU for short-term memory updater:

In dynamic graphs, recent neighbor interactions typically provide the most valuable information. While simple RNNs and K-neighbor aggregation fail to effectively capture these patterns (due to vanishing gradients and limited neighbor hops respectively), GRU's gating mechanism enables robust short-term dependency learning while complementing our ODE-based long-term capture. Our extended experiments confirm that simple RNN suffers from gradient vanishing, leading to performance degradation (mitigated by GRU’s gating mechanism). Besides, K-neighbor aggregation is limited to 1–2 hops, as wider aggregation blurs node representations.

Table 2: Trans.AP under different short-term memory updaters

c) MoE for long-short term fusion:

We propose MoE to fuse long-short term temporal correlations while adaptively selecting optimal backbones and weights per input. In temporal graphs, events exhibit mixed dependencies, but naive fusion methods (e.g., concatenation, voting) treat edges uniformly, ignoring their distinct evolutionary patterns. MoE addresses this by dynamically routing events to specialized experts based on node/edge features, achieving superior performance (see Table). For instance, on USLegis, MoE improves Trans.AP by 15.3% over concatenation and 16.2% over voting, demonstrating its ability to capture varied temporal scales.

Table 3: Trans.AP under different long-short term fusers

d) Co-occurrence encoder as structure encoder:

Our co-occurrence encoder efficiently captures structural patterns while maintaining computational feasibility. Unlike traditional methods that trade off expressiveness for efficiency, it encodes neighbor co-occurrence frequencies as relative structural features, enhanced by a hash-based memory system for accelerated processing. Experiments demonstrate its superiority over basic message passing and random walk approaches, with significantly better performance at manageable computational cost.

Table 4: Trans.AP with different structure encoders

d) IB for feature fusion:

Temporal graphs require effective fusion of temporal and structural features, which often conflict when combined naively. Our solution adapts the Information Bottleneck method to: (1) create unified node representations, (2) perform data-aware dimensionality reduction, and (3) filter noise while preserving critical temporal-structural information. This approach outperforms naive fusion methods by resolving feature conflicts and optimizing representation quality (as justified in Fig.3).

W1&W3&Q1&Q2: Writing issues

We sincerely appreciate your careful review. We are currently: (1) reorganizing key sections, (2) clarifying mathematical explanations, and (3) correcting all identified inconsistencies. A thorough proofreading will ensure these issues are resolved in the final version.

W2&Q5: Neural ODEs rationale

Thanks for your insightful advice. We further justify the introduction of Neural ODEs. Unlike RNNs' discrete Backpropagation Through Time (BPTT), which triggers gradient vanishing. ODE-based methods excel in dynamic graphs by: (1) enabling continuous memory updates for irregular timestamps, and (2) preventing gradient vanishing through second-order derivative integration. To be specific, gradient computation in ODEs employs the adjoint method, where gradients are calculated by solving an augmented ODE backward. For instance, the adjoint state $a(t) = -\frac{\partial\mathscr{L}}{\partial h(t)}$ has a time derivative given by $\frac{da(t)}{dt} = -a(t)^T \frac{\partial f(t, h(t), \theta_t)}{\partial h(t)}$, ensuring gradient stability through integration.

W4: Batch size impact

Thanks for your insightful advice. We acknowledge the performance trade-off with larger batches, a common challenge for memory-based methods. Our experiments show SALoM maintains better accuracy than TGN across batch sizes (see results below), though both are affected by information loss. While training optimizations could mitigate this, our focus remains on model design.

Table 5: Trans.AP comparison under different batch sizes

W5&Q4: MoE configuration analysis

Thanks for your insightful advice. The extended experimental results are as below. Our experiments show that MoE hyperparameters (expert count Q and selection count r) generally have minimal impact on performance, with two exceptions: (1) selecting only one expert degrades performance (e.g., −15% AP on USLegis) due to lost feature fusion, and (2) excessive experts underfit small datasets (e.g., USLegis). Computational costs scale predictably: VRAM grows linearly with Q (+2.7MB/expert), while training time increases sublinearly (~0.02s → 0.027s/iter for 4→8 experts). The optimal balance is 6 experts with 2 selected, achieving peak accuracy (e.g., 93.86 AP on Untrade) with moderate resource use (18.67MB VRAM). We will incorporate these findings in the final version.

Table 6: Trans.AP under different number of selected and total experts

Table 7: Train time and GPU memory usage under different numbers of selected and total experts

Q3: Single hashmap impact

Thank you for your valuable feedback. Our extended experiments confirm the limitations of using a single hashmap. The dual-memory structure (long-term and short-term) effectively captures both historical and recent neighbor records while reducing hash collision effects. A single hash table would degrade feature extraction, worsen collision impacts, and produce less distinguishable embeddings, ultimately harming performance. The results below support this conclusion.

Table 8: Trans.AP under using SingleHash and DualHash

We are glad that the reviewer appreciates our work from the perspective of novelty and performance. Thank you for pointing out the weak motivation issue. We have carefully revised the manuscript according to your constructive suggestions. Below we address the main points raised in the review.

W1：Individual motivations:

We apologize for any confusion and now provide analytical and experimental motivation for each SALoM component:

a) ODE-based memory updater for long-term temporal correlation:

Traditional sequential methods (RNNs/GRUs) treat dynamic graphs as discrete events, struggling with temporal continuity and long-term dependencies due to gradient issues. In contrast, ODE-based methods preserve continuity and avoid gradient issues through second-order derivative integration, demonstrating superior long-term dependency capture with minimal information loss (Table 1, [1]). This experiment is designed to predict the label(-1/1) of the first node with node embedding propagated through a linear graph of length(n). However, our ablation studies (Fig. 2) show that over-emphasizing long-term dependencies can cause over-globalization. We therefore propose LSMU, an MoE-based approach that dynamically balances long/short-term dependencies, adaptively selecting the optimal processing.

Table 1: Accuracy under different numbers of sampling neighbors

[1]GRAVINA, Alessio, et al. Long range propagation on continuous-time dynamic graphs. arXiv preprint arXiv:2406.02740, 2024.

b) GRU for short-term memory updater:

In dynamic graphs, recent neighbor interactions typically provide the most valuable information. While simple RNNs and K-neighbor aggregation fail to effectively capture these patterns (due to vanishing gradients and limited neighbor hops respectively), GRU's gating mechanism enables robust short-term dependency learning while complementing our ODE-based long-term capture. Our extended experiments confirm that simple RNN suffers from gradient vanishing, leading to performance degradation (mitigated by GRU’s gating mechanism). Besides, K-neighbor aggregation is limited to 1–2 hops, as wider aggregation blurs node representations.

Table 2: Trans.AP under different short-term memory updaters

c) MoE for long-short term fusion:

We propose MoE to fuse long-short term temporal correlations while adaptively selecting optimal backbones and weights per input. In temporal graphs, events exhibit mixed dependencies, but naive fusion methods (e.g., concatenation, voting) treat edges uniformly, ignoring their distinct evolutionary patterns. MoE addresses this by dynamically routing events to specialized experts based on node/edge features, achieving superior performance (see Table). For instance, on USLegis, MoE improves Trans.AP by 15.3% over concatenation and 16.2% over voting, demonstrating its ability to capture varied temporal scales.

Table 3: Trans.AP under different long-short term fusers

d) Co-occurrence encoder as structure encoder:

Our co-occurrence encoder efficiently captures structural patterns while maintaining computational feasibility. Unlike traditional methods that trade off expressiveness for efficiency, it encodes neighbor co-occurrence frequencies as relative structural features, enhanced by a hash-based memory system for accelerated processing. Experiments demonstrate its superiority over basic message passing and random walk approaches, with significantly better performance at manageable computational cost.

Table 4: Trans.AP with different structure encoders

d) IB for feature fusion:

Temporal graphs require effective fusion of temporal and structural features, which often conflict when combined naively. Our solution adapts the Information Bottleneck method to: (1) create unified node representations, (2) perform data-aware dimensionality reduction, and (3) filter noise while preserving critical temporal-structural information. This approach outperforms naive fusion methods by resolving feature conflicts and optimizing representation quality (as justified in Fig.3).

W2：Performance in inductive setting

Although SALoM exhibits a slight performance decline in inductive settings due to its relatively higher reliance on prior knowledge, it still achieves state-of-the-art (SOTA) performance on most datasets. Notably, it achieves an AP above 85 on the UNtrade dataset, and overall, it remains the most effective method on average across all datasets.

Q1: Num of experts

Thanks for your insightful advice, we have extended our experiments on more hyperparameter settings of LSMU module as below.

For the results, we discover that in general, the hyperparameters of MoE module hold rather small impact on model performance. However, a few anomalies are discovered. First, as observed in the third row, selecting only one expert per iteration—an unconventional setting—leads to performance degradation due to the lack of fusion between long-term and short-term temporal features, resulting from selecting a single backbone for all edges in a batch. Second, the experimental setup in the last row shows poor performance on the USLegis dataset, attributed to an insufficient dataset size to meet the demands of each expert, causing all experts to be underfitted.

Table 5: Trans.AP under different number of selected and total experts

Q2: Performance degrade as the number of historical neighbors increase

We appreciate this important observation. The performance degradation with increasing historical neighbors occurs because: (1) larger neighbor samples lead to higher similarity between nodes during aggregation, reducing embedding distinctiveness and potentially causing over-globalization; (2) for memory updates, iterate mechanisms already preserve long-term information, making excessive sampling counterproductive as it disproportionately weights long-term dependencies at the expense of crucial short-term patterns.