Read the paper
Interpreting Timestamp Permutations in Dynamic Link Prediction
on GitHub
Imagine you're testing whether a chess player uses the clock. You scramble the time display and notice they play worse. Obvious conclusion: they relied on time information. But wait — you also changed their practice conditions. Did they play worse because they can't see the clock during the game, or because they trained without it and never learned certain strategies? This paper is about pulling those two effects apart in dynamic link prediction, and the answer turns out to be lopsided. The core claim: standard timestamp-permutation tests for dynamic graph neural networks confound two distinct effects — changes to the training regime and changes to the evaluation-time history. The authors introduce a crossed diagnostic that separates them. Train with original or permuted timestamps, then evaluate under original or permuted history, yielding a 2×2 matrix instead of a single before/after number. The results are striking: on the MOOC dataset, TCL trained with BCE gains ~8 pairwise-accuracy points from original-chronology training regardless of which evaluation history you use. But swapping the history at fixed weights moves the needle only 0.03 points. The permutation test was measuring training, not inference. Why is the history effect so tiny? The paper introduces 'input exposure' — measuring whether permuted histories actually change the model's inputs at query time. On MOOC, 68.37% of queries receive identical neighbor sets under both chronologies. For the rest, ranking changes largely cancel out in aggregate. The model literally cannot tell the difference for most of its test queries. This is a measurement problem hiding inside what looked like a modeling question. DyGFormer, an attention-based architecture, shows the same pattern at larger scale: 22.34-point training contrast, 0.38-point history contrast, across two seeds — despite having greater input exposure to the permutation. Explicit time encoding accounts for a measurable but partial share: suppressing it reduces the training contrast from 8.03 to 3.64 points (paired reduction 4.39, 95% CI [3.68, 5.09] over six seeds). So temporal features matter, but not as the sole channel. The partial-permutation experiments add further resolution by separating nominal intervention strength (how much you shuffle), actual input changes (what the model sees), and aggregate accuracy shifts. These can diverge substantially, which is the methodological point: a single permutation gap is an unreliable summary statistic because it conflates at least three distinct quantities. This is a methods-diagnostic paper, not a new architecture or a SOTA claim. Its contribution is showing that a widely used evaluation protocol was measuring the wrong thing — or rather, measuring a mixture of things that researchers were interpreting as one. The practical upshot: anyone running timestamp permutation tests on dynamic link predictors should adopt the crossed design and report input exposure. The paper is compact (5 pages, ACM sigconf) and ships code with trained models. What the paper does not do is explain the internal mechanisms by which temporal information improves training. It explicitly leaves that open. The crossed diagnostic tells you where the signal lives (training vs. inference) but not how the model uses it. That's the successor experiment — and probably the next paper.
The analogy
You're testing whether a chef uses salt by removing it. But you removed it from the pantry during their training year AND from the table on test night. When they cook worse, you don't know which removal caused it. This paper separates the pantry from the table.
Salt test
Remove salt from training pantry AND test table simultaneously, then attribute the entire cooking decline to 'the chef uses salt'
Timestamp permutation
Permute timestamps during training AND evaluation simultaneously, then attribute the entire accuracy drop to 'the model uses temporal info'
Honest assessment
A clean, narrowly scoped methods paper that identifies a real confound in a widely used evaluation protocol. The crossed diagnostic is elegant and the input-exposure concept is genuinely useful. The limitation is that everything rests on one dataset and low seed counts — the finding needs replication across the standard temporal graph benchmarks before it reshapes practice. If you run timestamp permutation tests, read this. If you don't, it's skippable.
What Is CLAIMS?
63
/ 100
BedrockNews applies a structured analytical framework called CLAIMS to academic papers and technical research releases.
How CLAIMS worksClaim
4/5
Ladder
3/5
Architecture
3/5
Integrity
3/5
Milestone
3/5
Successor
3/5
What is this paper actually committing to?
Genuine methodological contribution: standard permutation tests confound two effects. Not a new model, but a new diagnostic that changes how you read existing results. Important if adopted.
The field fight
Do dynamic link predictors actually learn temporal patterns, or do they succeed via non-temporal structural features that happen to correlate with time?
Side A
Timestamp permutation tests show models exploit temporal info — the accuracy drop when you shuffle proves it
Held by: TGN, TGAT, TCL evaluation protocols
Side B
The permutation gap is confounded — it conflates training-regime effects with actual temporal inference, and much of the gap comes from training, not history reading
Held by: This paper
Milestone tracker
Unlocks: Formal deprecation of single-gap permutation protocol; reliable temporal-learning claims across the field
Current
1
dataset
MOOC crossed diagnostic
Next
5+
datasets
Standard TG benchmarks
~6-12 months; compute is modest, need community uptake
Verified Facts (6)
TCL trained with BCE gains approximately eight pairwise-accuracy points from original-chronology training under either evaluation history
Changing history at fixed weights gives only 0.03 points
68.37% of queries receive unchanged inputs under permutation
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 training and history contrasts of 22.34 and 0.38 points across two seeds
5 pages total (ACM sigconf format)
Practical Implications (3)
Anyone running timestamp-permutation ablations on dynamic link predictors should adopt the 2×2 crossed design (train × eval) instead of a single shuffle-vs-original comparison
Report input exposure (percentage of queries with unchanged neighbor sets) alongside any permutation gap — without it, a small gap may reflect unchanged inputs, not temporal irrelevance
Published permutation results on MOOC (and likely other datasets) should be reinterpreted as primarily reflecting training-regime effects, not inference-time temporal processing
More latest news
Read all