betaFeedback

WorksComputer Science

Interpreting Timestamp Permutations in Dynamic Link Prediction

Abstract

Timestamp permutations are used to test whether dynamic link predictors exploit temporal information, but a performance gap can reflect changes in training, evaluation history, or both. We separate these effects with a crossed diagnostic and measure input exposure: whether altered histories actually change the predictor's inputs. On MOOC, TCL trained with binary cross-entropy gains approximately eight pairwise-accuracy points from original-chronology training under either evaluation history, while changing history at fixed weights gives only 0.03 points. The small history contrast reflects unchanged inputs for 68.37% of queries, stable rankings for most others, and cancellation of gains and losses. Under original evaluation history, suppressing explicit time encoding reduces the training contrast from 8.03 to 3.64 points, a paired reduction of 4.39 points (95% interval [3.68, 5.09]) across six seeds. DyGFormer shows corresponding training and history contrasts of 22.34 and 0.38 points across two seeds, despite greater exposure. Partial history permutations further separate nominal intervention strength, input changes, and aggregate accuracy. These comparisons turn a single permutation gap into interpretable statements about training conditions and model responses, while leaving the internal mechanisms of temporal learning open.

CCS Concepts • Information systems → Data mining; • Computing methodologies → Machine learning.

Introduction

A drop in dynamic link-prediction accuracy after permuting timestamps is often interpreted as evidence that a model uses temporal information [7]. This test reassigns event times while preserving interacting pairs and non-temporal attributes: useful recency or ordering relationships may disappear even though the observed interactions remain. The difficulty is deciding what the resulting gap measures. Retraining on permuted events changes the learning procedure; supplying a changed history to fixed weights changes evaluation inputs. A single comparison that changes both cannot separate their effects.

A small gap is also ambiguous. A predictor that selects recent neighbors may never receive the altered events because later interactions displace them. Even when inputs change, candidate rankings may remain stable, and opposing ranking changes may cancel in aggregate accuracy. Interpretation therefore requires following the intervention from event history through model inputs to predictions.

Existing work tests fixed models on distorted evaluation data [7], examines timestamp granularity [2], and evaluates causal shifts using known graph generators [6]. We add a controlled comparison of training and evaluation-history interventions, together with direct checks of the inputs they change. This matters for benchmarking [3, 9]: high predictive quality can also arise from edge memorization [5] or recency/popularity heuristics [1]. Our paired experiments across four public datasets show widely varying permutation sensitivity, motivating a closer analysis of what each gap contains.

We ask three questions. How much of a permutation gap comes from training versus evaluation history? When do altered histories change inputs and rankings, and how does intervention strength affect that response? How do explicit time encoding, architecture, and candidate construction shape these conclusions?

Our contribution is a reproducible, crossed, exposure-aware diagnostic that answers these questions through separate contrasts and input tracing. A six-seed study of TCL with binary cross-entropy (TCL-BCE) on the massive open online course (MOOC) dataset [4] connects these measurements to a matched time-encoding ablation. DyGFormer and logistic controls test the diagnostic’s applicability and distinguish model sensitivity from useful chronology in the prediction task.

Diagnostic Design

Crossing training chronology and history

The diagnostic varies two factors independently. Training chronology is the original or permuted chronology used to learn weights. Evaluation history is the original or permuted history used to construct the trained model’s inputs. Their four combinations are shown below.

Evaluation history
Training chronologyOriginalPermuted
OriginalAB
PermutedCD

A uses original training and original evaluation history. B evaluates the same original-trained model with permuted history. C uses permuted training and original evaluation history. D evaluates the same permutation-trained model with the corresponding permuted history. All four conditions use identical test queries, query timestamps, and positive/negative candidates. A→B and C→D change only evaluation history, with no retraining.

For seed ss and permutation π\pi, let θs,0\theta_{s,0}, θs,π\theta_{s,\pi} be the selected original-trained and permutation-trained weights, and H0H_0, HπH_\pi the evaluation histories. For performance measure MM, the conditions are

A=M(θs,0,H0),B=M(θs,0,Hπ),C=M(θs,π,H0),D=M(θs,π,Hπ).\begin{aligned} A &= M(\theta_{s,0}, H_0), \qquad B = M(\theta_{s,0}, H_\pi),\\ C &= M(\theta_{s,\pi}, H_0), \qquad D = M(\theta_{s,\pi}, H_\pi). \end{aligned}

Training-procedure contrasts (A–C and B–D). A–C compares original- and permutation-trained models under common original history; B–D compares them under the corresponding common permuted history. These contrasts may reflect temporal features, neighborhoods, optimization order, checkpoint selection, or mismatch between training and evaluation histories.

A–B and C–D: fixed-weight history contrasts. A–B measures the effect of changing history for the original-trained model; C–D measures the same intervention for the permutation-trained model. Their difference,

I=(A−B)−(C−D),(1)I = (A - B) - (C - D), \tag*{(1)}

is the interaction, also equal to (A−C)−(B−D)(A - C) - (B - D): does the response to evaluation history depend on training chronology? A–D, the joint contrast, changes training chronology and evaluation history simultaneously. The identity A−D=(A−C)+(C−D)A - D = (A - C) + (C - D) splits the joint gap into a training contrast under common history and a fixed-weight history contrast.

We freeze the chronological split and node-exclusion rule. Permutations reassign timestamps within MOOC’s 288,224-event pre-split history, preserving endpoints and features. Training uses the same 227,485 eligible events; excluded-node events can still enter history. Histories contain only events strictly preceding the query, and validation/test events retain their original times.

Input exposure and prediction quality

TCL-BCE uses only the 20 most recent interactions for each endpoint. Later validation and test events can push altered training events outside this window, leaving a query’s inputs unchanged. For these queries, A–B cannot test the response to altered temporal information.

For each query, compare the tensors supplied under H0H_0 and HπH_\pi for the source and both candidates. For TCL-BCE these include ordered node/edge features, time differences, and padding masks. Input exposure is the fraction of queries for which any compared input changes. The unchanged-input group has identical inputs across all tested histories. At fixed weights, equal inputs imply equal predictions up to numerical precision. Graded exposure dqd_q divides changed history positions by positions nonempty in either history, summed over source and both candidates (zero if empty). A position changes when its features, time difference, or padding changes.

Pairwise accuracy credits one when the positive candidate outranks the negative and one half for a tie. Pooled average precision (AP) also ranks examples across queries. To diagnose query offsets, subtract each query’s mean logit from both logits and recompute AP. This label-free centering preserves within-query rankings but does not decompose AP additively. Accuracy and AP contrasts use percentage points; absolute AP uses the 0–1 scale.

Experiments and Findings

Controlled TCL-BCE evaluation

We evaluate DyGLib-based TCL-BCE [8, 9] on MOOC learner–resource interactions [4]. All 61,763 test queries have one fixed random negative, including 670 positive–negative collisions. Training negatives are keyed by event ID, seed, and epoch over a fixed destination pool, so they match across chronologies for each event and shared epoch.

For each of six seeds (1004–1009), we train on original chronology and five permutations. Checkpoints use the earliest strict maximum of pooled validation AP, with 20–100 epochs and patience 10. We average permutation contrasts within seed; descriptive 95% tt intervals use six seed means as uncertainty units.

All experimental code and trained models are available for download from the project repository at https://github.com/karpovilia/tgn.

Separating training and history effects

Original training improves pairwise accuracy under both common evaluation histories: by 8.03 points with original history (A–C; 95% interval [7.65, 8.41]) and 7.95 with permuted history (B–D; [7.59, 8.31]). Both are positive in every seed. Changing only the original-trained model’s evaluation history gives a 0.03-point contrast (A–B). The joint A–D gap of 7.98 points mainly reflects the training contrast. The interaction is 0.074 points, with a 95% interval of [0.023, 0.125]. The A–C advantage is also positive in every seed for pooled AP (13.50 points) and centered AP (9.71 points; intervals in the artifact). Excluding candidate collisions retains an 8.11-point accuracy contrast [7.73, 8.50] and 13.83 AP points over 61,093 queries.

To understand the small history contrast, we first check whether the intervention reaches the model. Each permutation changes inputs for the same 19,533 queries (31.63%); the other 42,230 (68.37%) retain identical inputs. Exposure falls from 39.15% in the first equal-count test decile to 14.04% in the last.

Exposure does not guarantee a ranking change. Only 2.77% of exposed queries change ordering (0.875% of all queries), and opposing gains and losses leave an A–B contrast of 0.095 points; C–D is −0.139 points in this group. Unchanged inputs produce no history-induced ranking flips in either training condition. Their maximum logit drift is 6.63 × 10−610^{-6} across 60 comparisons, within the pre-specified tolerance 2×10−5+10−5(∣z0∣+∣zπ∣)2 \times10^{-5} + 10^{-5}(|z_0| + |z_\pi|). The small contrast combines unchanged inputs, stable rankings, and cancellation.

A–C is positive in every seed for unchanged-input queries (9.50 points) and exposed queries (4.85 points; Figure 1). The training advantage persists where history interventions leave inputs untouched. These groups differ in composition.

Figure 1. TCL-BCE input exposure and accuracy contrasts. (a) Queries with changed or identical inputs. (b) A–C: blue means and six seed dots; A–B: orange diamonds at fixed original-trained weights. Contrasts average five permutations within seed and are in percentage points. Input-defined groups differ in composition.

Graded exposure. Input changes also vary in intensity. With original-trained weights, ranking flips rise from 2.19% [1.91, 2.47] for 0<dq≤0.250 < d_q \le0.25 to 4.77% [4.05, 5.49] for 0.25<dq≤0.50.25 < d_q \le0.5; mean absolute changes in the positive-minus-negative logit margin rise from 0.197 to 0.458. Intervals use six seed means, each averaging five permutations. About 15,160 and 4,343 queries per permutation fall in these groups; only 30 have dq>0.5d_q > 0.5. Differing temporal composition makes this comparison descriptive.

We then vary intervention strength while holding weights fixed, permuting timestamps within nested random subsets of the history prefix, with fractions α∈{0,.25,.5,.75,1}\alpha\in\{0, .25, .5, .75, 1\}. Selected events are ordered by their positions in the full permutation and assigned, in that order, to their selected original timestamp slots in chronological order. Unselected events keep their timestamps; α=0\alpha= 0 is identity and α=1\alpha= 1 is the full permutation.

Both original-trained and full-permutation-trained weights stay fixed across the six seeds and five permutations. From α=.25\alpha= .25 to 1, mean exposure increases from 27.91% to 31.63%, while all-query ranking flips increase from 0.585% to 0.875% at original-trained weights; the corresponding accuracy contrasts remain 0.022–0.033 points across nonzero levels. Thus a stronger event-level intervention can change more rankings while leaving aggregate accuracy nearly unchanged. History construction also matters: exposure is 12.01%, 18.54%, 31.63%, and 62.64% at 5, 10, 20, and 50 neighbors. This checks which inputs are reached, without comparing model quality across history lengths.

Explicit time encoding

To test how the training advantage depends on explicit time encoding, we repeat A–D with zero time-encoder outputs during training and inference. Model layout, architecture, neighborhood construction, timestamp sorting, candidates, and checkpoint selection are preserved. Nine OFF models from the three-seed, two-permutation validation pilot are reused.

With encoding OFF, A–C falls from 8.03 to 3.64 points [2.91, 4.37] (Table 1). Define

ConfigurationSeedsABCDA–CB–DA–BC–DII
TCL-BCE ON681.9081.8773.8773.928.037.950.03−0.040.07
TCL-BCE OFF670.0069.9266.3666.393.643.530.08−0.030.11
DyGFormer100486.9086.5464.6464.3722.2722.170.370.270.10
DyGFormer100586.9586.5764.5464.2922.4222.270.390.240.14

Table 1. Crossed MOOC diagnostic. A–D: pairwise accuracies (%); contrasts: percentage points, computed before rounding. TCL-BCE averages five permutations within each seed, then six seeds. DyGFormer reports seed means. ON/OFF: explicit time encoding during training and inference. AP, centered AP, individual permutations, and intervals are in the artifact.

Δtime=(A−C)ON−(A−C)OFF.\Delta_{\mathrm{time}} = (A-C)_{\mathrm{ON}} - (A-C)_{\mathrm{OFF}}.

The paired reduction is 4.39 points [3.68, 5.09], positive for all six seeds. Removing candidate collisions gives a 4.43-point reduction [3.72, 5.15]. AP and centered AP give positive paired reductions of 7.49 and 4.97 points. Removing explicit time encoding reduces the measured contrast by 54.7%. Because the ablation changes the fitted predictor, this is component sensitivity, not a causal decomposition of learned temporal information. The remaining contrast may involve temporal neighborhoods and optimization order.

Transfer to DyGFormer

To test applicability beyond TCL-BCE, we apply A–D to DyGFormer [9] on the same split, queries, and candidates. Seeds 1004 and 1005 form a hardware-defined block independent of test effects, each with five permutations. Training uses BCE, 256-event sequences, and TCL-BCE’s selection and epoch rules. Negatives follow the same event-ID/seed/epoch schedule and fixed destination pool across chronologies. A two-permutation validation pilot preceded test evaluation. We report seed means separately because permutations sharing a seed are dependent.

The A–C accuracy contrasts are 22.27 and 22.42 points; A–B is 0.37 and 0.39 points (Table 1). DyGFormer’s input trace includes node/edge/time features, padding, and neighbor co-occurrence counts; hashes are compared only at fixed weights. The history intervention exposes 87.53% of queries, compared with 31.63% for TCL-BCE, and changes candidate ordering for 3.93% of exposed queries (3.44% of all queries) under original-trained weights. The 256-event DyGFormer sequences and 20-interaction TCL-BCE histories differ in available context, so exposure differences concern these configurations. Equal inputs preserve rankings in every checked comparison. Excluding candidate collisions retains the positive training-procedure contrast in both seeds. The protocol therefore transfers across architectures: even with greater exposure, stable rankings and cancellation keep the history contrast much smaller than the training contrast.

Recency and multi-dataset comparisons

The neural contrasts describe model responses; logistic controls ask whether chronology supplies useful predictive features under matched candidates. Full-batch logistic regression compares a six-feature baseline with the same features plus ages since last occurrence. The six baseline features are pair, source, and destination interaction counts, with three corresponding seen indicators. Counts and ages are log-transformed, ages use a TRAIN-derived time scale, and standardization uses TRAIN only. Feature and optimizer specifications are in the artifact.

Original/permuted fits share training queries, row order, negative identities, and original causal evaluation history. Historical TRAIN negatives are destinations previously observed with the source in all compared histories; random negatives use the fixed TRAIN destination universe. Both exclude the positive candidate. Queries lacking a common historical alternative are excluded from both protocols but retained as history events. At test time, historical negatives precede the query; random negatives use the same universe. Both protocols evaluate 60,630 MOOC and 14,515 Wikipedia queries after exclusions and collision removal. Each chronology comparison fixes candidates within its protocol; absolute accuracy across these different prediction tasks is not a measure of model superiority.

Let Δages\Delta_{\mathrm{ages}} and Δcounts\Delta_{\mathrm{counts}} be original-minus-global-permutation accuracy contrasts, and Δrecency=Δages−Δcounts\Delta_{\mathrm{recency}} = \Delta_{\mathrm{ages}} - \Delta_{\mathrm{counts}}. Across ten paired draws, historical negatives yield positive recency contrasts on

MOOC (33.90 points [33.18, 34.61]) and Wikipedia (16.15 [15.41, 16.89]). With random TRAIN/test negatives, MOOC retains a 14.17-point contrast [13.99, 14.35], positive in every draw (Table 2). Recency utility therefore survives this change of candidate distribution, although its magnitude changes. A three-draw validation pilot preceded the frozen random-protocol evaluation. This MOOC population passes the recorded composition checks: less than 95% unseen negatives, at least 1,000 both-seen queries, and accuracy below 95% for a rule using pair-seen status alone, in every draw. On Wikipedia, random negatives yield a 1.63-point recency contrast [0.99, 2.28]. In every draw, unseen negatives exceed 95% and fewer than 1,000 queries have both candidates seen. We therefore restrict the random-sampling robustness claim to MOOC. Wikipedia results and windowed controls are reported in the artifact.

Dataset / negativesΔages\Delta_{\mathrm{ages}}Δrecency\Delta_{\mathrm{recency}}
MOOC / H32.67 [32.14, 33.20]33.90 [33.18, 34.61]
MOOC / R17.21 [17.06, 17.36]14.17 [13.99, 14.35]

Table 2. MOOC logistic training-procedure contrasts (points), with 95% paired t9t_9 intervals over ten draws. H/R: historical/random negatives in both TRAIN and test. Queries are common across protocols; candidates are fixed within each chronology contrast.

Multi-dataset permutation experiments. Our 195 DyGLib original/permuted pairs cover five architectures and Wikipedia, Reddit, MOOC, and LastFM, using ten-epoch budgets, random negatives, one training-time permutation, and joint validation AP/AUC selection.

TCL-BCE original-minus-permuted AP gaps are 5.55, −0.12, 10.76, and 24.23 points on these datasets, respectively (nine unique pairs each).

On LastFM, DyGFormer achieves original AP 0.9245 with a 0.19-point gap, compared with AP 0.7552 and a 24.23-point gap for TCL-BCE (ten and nine pairs). Across all 20 model–dataset combinations, mean AP gaps range from −2.04 to 24.23 points: five are negative and ten have magnitude below 0.20 points. The four-dataset comparisons characterize variation in permutation sensitivity; the controlled MOOC experiments separate training-procedure and fixed-weight evaluation-history contrasts.

Interpretation and Scope

A–C and B–D measure the original training-procedure advantage under common original and permuted histories, respectively. The ON/OFF ablation measures its dependence on explicit time encoding. A–B and C–D measure the response of fixed weights to altered history; exposure identifies which inputs can contribute, and ranking changes show how individual responses combine in accuracy. Graded and partial permutations connect intervention strength to these responses. These measurements explain why a small fixed-weight history contrast can coexist with a large training-procedure contrast.

Logistic controls address useful recency in a candidate-defined prediction task. The four-dataset comparisons describe variation across models and data. Neither substitutes for the crossed contrasts, and the component ablation does not identify a unique internal temporal-learning mechanism. Conclusions concern the evaluated configurations and candidate populations. Test data were previously examined, and pilots used the checkpoint-selection split. Intervals describe fixed-dataset seed/draw variability; DyGFormer reports two seed means.

Conclusion

Training chronology and evaluation history require separate analysis. For TCL-BCE, a large training-procedure advantage coexists with a small fixed-weight history contrast because many inputs remain unchanged, most exposed rankings are stable, and opposing changes cancel. Graded and partial permutations show how intervention strength reaches predictions, while time-encoding ablation reduces the training contrast without eliminating it. DyGFormer confirms the diagnostic’s applicability under a different exposure profile. Permutation studies should therefore report training and history contrasts, actual input exposure, and ranking changes, with uncertainty aggregated within training seeds.

Ethical Considerations

This study reuses public interaction benchmarks and reports aggregate model behavior. Reproducibility materials preserve pseudonymous identifiers and should respect source-data licenses without releasing additional identifying information. No individual-level behavioral claims are made. The diagnostic distinguishes measured protocol effects from claims about internal mechanisms or deployment performance. Generative artificial intelligence assisted code development and manuscript editing, including improvements to language and presentation. The authors take full responsibility for all content, including verifying its correctness and originality and ensuring proper attribution. Reported quantities were checked against experimental artifacts.

References

  1. [1]Filip Cornell, Oleg Smirnov, Gabriela Zarzar Gandler, and Lele Cao. 2025. On the Power of Heuristics in Temporal Graphs. In Proceedings of I Can’t Believe It’s Not Better: Challenges in Applied Deep Learning at ICLR 2025 Workshops (Proceedings of Machine Learning Research, Vol. 296). PMLR, 37–46. https://proceedings.mlr.press/v296/cornell25a.htmlarxiv.org/abs/2502.04910
  2. [2]Abigail J. Hayes, Tobias Schumacher, and Markus Strohmaier. 2025. What Do Temporal Graph Learning Models Learn? arXiv:2510.09416 doi:10.48550/arXiv.2510.09416 Version 4, revised July 2026.DOI
  3. [3]Shenyang Huang, Farimah Poursafaei, Jacob Danovitch, Matthias Fey, Weihua Hu, Emanuele Rossi, Jure Leskovec, Michael Bronstein, Guillaume Rabanser, and Reihaneh Rabbany. 2023. Temporal Graph Benchmark for Machine Learning on Temporal Graphs. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 36. 2056–2073. doi:10.52202/075280-0099DOI
  4. [4]Srijan Kumar, Xikun Zhang, and Jure Leskovec. 2019. Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). 1269–1278. doi:10.1145/3292500.3330895DOI
  5. [5]Farimah Poursafaei, Shenyang Huang, Kellin Perline, and Reihaneh Rabbany. 2022. Towards Better Evaluation for Dynamic Link Prediction. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 35. 32928–32941. doi:10.52202/068431-2386DOI
  6. [6]Aniq Ur Rahman and Justin Coon. 2026. Causal Temporal Graphs for Counterfactual Validation of Temporal Link Prediction. In Proceedings of The 1st Symposium on Probabilistic Machine Learning (Proceedings of Machine Learning Research, Vol. 327). PMLR, 119–134. https://proceedings.mlr.press/v327/rahman26a.htmlarxiv.org/abs/2602.02161
  7. [7]Aniq Ur Rahman, Alexander Modell, and Justin Coon. 2025. Rethinking Evaluation for Temporal Link Prediction through Counterfactual Analysis. In Proceedings on I Can’t Believe It’s Not Better: Challenges in Applied Deep Learning at ICLR 2025 Workshops (Proceedings of Machine Learning Research, Vol. 296). PMLR, 13–19. https://proceedings.mlr.press/v296/rahman25a.html
  8. [8]Lu Wang, Xiaofu Chang, Shuang Li, Yunfei Chu, Hui Li, Wei Zhang, Xiaofeng He, Song Jingren Zhou, and Hongxia Yang. 2021. TCL: Transformer-based Dynamic Graph Modelling via Contrastive Learning. arXiv:2105.07944 doi:10.48550/arXiv.2105.07944DOI
  9. [9]Le Yu, Leilei Sun, Bowen Du, and Weifeng Lv. 2023. Towards Better Dynamic Graph Learning: New Architecture and Unified Library. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 36. 67686–67700. doi:10.52202/075280-2960DOI

Paper details

vlnc:W_xgmxhux5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents