Step-Doubling Snapshots: Letting the Model Choose Its Own Clock in Temporal Knowledge Graphs

Temporal knowledge graphs store facts with a timestamp, such as "(Country A, threatens, Country B, 2014-03-02)". Models that forecast future facts almost always first chop time into fixed bins, typically one day, and update an internal state once per bin. That choice is arbitrary. In a quiet month, most daily bins are nearly empty, and each update adds noise and one more step for errors to compound over during multi-step forecasts. In a crisis week, hundreds of causally ordered events land in one bin and are treated as simultaneous. Numerical simulation met the same problem long ago and solved it with adaptive step sizes: take large steps where the solution is smooth and small ones where it changes fast, and decide which is which with a cheap error check. The most classical check is step doubling. You take one full step and two half steps over the same interval and shrink the step if the two results disagree.

This note proposes carrying step doubling into temporal knowledge graphs. We would apply it to the placement of the snapshot boundaries at which the model absorbs events, not to an ODE solver's internal step. For any candidate interval, the model ingests its events once as a single aggregated update and once as two half-interval updates. If the two resulting forecasts disagree by more than a tolerance, the interval is split. If they agree, neighboring intervals are merged. The claim is that this model-driven, data-dependent clock gives better long-horizon forecasts with fewer state updates than any fixed bin width. It should also beat the obvious cheap adaptive rule of bins holding equal numbers of events. If equal-count binning matches it, the idea is wrong, and the experiments are designed to show this plainly.

Core Claim

The closest continuous-time work adapts in the wrong place. TANGO evolves entity embeddings with a neural ordinary differential equation (a network that defines the time derivative of a hidden state, integrated by a numerical solver) between graph snapshots, and names "more advanced adaptive ODE solvers" as future work. LAMP treats snapshot arrivals as instantaneous jumps in an otherwise continuous flow, an impulsive ODE, and flags its fixed forward-Euler step as a limitation. Both inherit the snapshot grid from the dataset. Between observed events, the learned flow is usually smooth, so an adaptive solver there mostly changes the number of function evaluations. It does little about the discretization error that matters, which is how events are grouped into jumps. TransformerG2G calls its attention over past snapshots "adaptive time-stepping," but it only reweights a fixed grid of bins.

Our proposal differs in three ways. It adapts the jump times themselves. It uses an explicit consistency test rather than learned attention. It applies the same test during forecasting, where the model must choose how far to step into a future with no observed edges. The method comes from Adaptive Choice of Grid and Time in Reinforcement Learning, which contracts the step when a full-step and two-half-step value update disagree. We transplant that test from value functions to relational state.

Research Program

The base model is a LAMP-style impulsive ODE on a multi-relational graph. A relational graph convolution encoder, as in TANGO, turns the events in an interval into an update of entity states. Between updates, a smooth learned flow carries the states forward. A TuckER decoder (TuckER) scores candidate objects. The new component is the grid controller.

Let $I=[a,b]$ be a candidate interval, and let $p_{\text{full}}(\cdot \mid q)$ and $p_{\text{half}}(\cdot \mid q)$ be the model's predicted object distributions for a probe query $q$ at time $b$. The first comes from one aggregated update over $I$. The second comes from two updates over $[a,\tfrac{a+b}{2}]$ and $[\tfrac{a+b}{2},b]$. The error indicator is

$$ e(I) = \frac{1}{|Q_I|}\sum_{q \in Q_I} \mathrm{KL}\big(p_{\text{half}}(\cdot\mid q)\,\|\,p_{\text{full}}(\cdot\mid q)\big), $$

where $Q_I$ is a set of probe queries built from entities active in or near $I$. Intervals with $e(I)>\tau$ are split and pairs with $e<\tau/4$ are merged. A floor at the dataset's native granularity prevents collapse. The factor of four mirrors the classical rule for a first-order scheme, whose local error roughly halves when the step halves.

Training alternates two phases. The model trains on the current grid for a few epochs, then the controller rebuilds the grid from the current model. The grid is frozen within a phase so gradients never pass through the discrete split decisions. The tolerance $\tau$ sets the accuracy/compute trade-off.

During forecasting, the controller runs on the model's own predicted events rather than observed ones. This lets the model take long strides through predicted quiet periods and short ones through predicted volatility, which should reduce the error cascades of fixed-step autoregressive rollouts.

We will also study the analysis side. We will measure whether the learned grid concentrates resolution around known bursts, such as conflict onsets in ICEWS. We will also check whether the grid is stable across random seeds, because a clock that changes with the seed would be hard to interpret.

Baselines

The naive reference is the same impulsive-ODE model on the dataset's native daily grid. The second baseline uses the best single fixed bin width chosen on validation from a sweep of one, two, four, seven and fourteen days. This oracle-tuned fixed grid is what a careful practitioner would do. Adaptivity only matters if it beats that sweep, not just the default.

The strongest existing continuous-time forecaster is TANGO. The file reports TANGO-TuckER at MRR 42.86% on ICEWS05-15, along with roughly 12x faster training than RE-Net (TANGO). We will rerun TANGO with its released protocol so the comparison is not against a number produced under different filtering. We will run it twice, with its fixed-step solver and with an adaptive Dormand–Prince solver. That second run tests the TANGO authors' own suggested extension directly.

On the strict chronological splits, the reference is TDSym. It reports MRR ≈ 0.362 on ICEWS14-Ext and ICEWS05-15-Ext, while discrete lookup-table models score near zero there (TDSym). TDSym solves a different problem: it completes facts at unseen times through a continuous Hamiltonian embedding and never groups events. It is therefore a reference point for extrapolating to unseen timestamps, not a like-for-like forecaster.

Two ablations isolate the key ingredient. The first is equal-event-count binning with the same total number of bins as the adaptive grid. The second is a random grid with the same bin count. Every variant shares the encoder, the decoder, a fixed GPU-hour budget, and an equal number of hyperparameter trials, and every variant gets its bin count or $\tau$ tuned on validation.

Counting as a win means two things at a matched number of state updates. The first is higher filtered MRR than the tuned fixed grid and than equal-count binning, with a gap larger than seed variance. The second is a widening of that advantage at longer forecast horizons.

Why not just…?

Why not just drop an adaptive solver like Dormand–Prince into TANGO? This is exactly what TANGO's authors suggested, and we run it. Our prediction is that it changes compute more than accuracy. The flow between events is smooth, and the stiffness that makes explicit adaptive solvers collapse their step sizes (Bayesian differential programming, Opening the Blackbox) comes from the jumps, not from the flow. The comparison settles this. If adaptive-solver TANGO closes the gap, the proposal's premise that grouping error dominates is refuted.

Why not just bin by equal event counts? This is the most serious threat. Equal-count binning already shrinks bins in busy periods, it needs no model, and it may capture most of the benefit. It differs from our controller in one way. It reacts to event volume, while the step-doubling test reacts to whether splitting changes the forecasts. A week of routine repeated statements is high volume but low information; a single surprising event is low volume but high information. Equal-count binning is a baseline with matched bin count. If it matches the adaptive grid, we will report that the gain comes from volume-aware binning and drop the error-indicator claim.

Why not just update at every event, as point-process models do? Know-Evolve updates entity states at every event arrival, which removes binning entirely. With daily ICEWS timestamps, though, many events share a timestamp. Per-event updates then impose an arbitrary order and multiply the number of updates. We include a per-event variant of our model, sequential within a day in random order, to measure both costs.

Why not just let attention weight the history? TransformerG2G's attention reweights a fixed window of pre-binned snapshots. It cannot place a boundary inside a bin or choose a stride during forecasting. We test a transformer over the daily grid with the same budget.

Proposed Experiments

The main benchmarks are ICEWS14, ICEWS18 and ICEWS05-15 under the standard forecasting protocol. We add TANGO's irregularly sampled ICEWS05-15, where fixed grids are most mismatched, and the chronological ICEWS14-Ext and ICEWS05-15-Ext splits. YAGO and WIKI use coarse yearly intervals, and existing models already exceed 0.9 Hits@10 there (Towards Better Evolution Modeling). We report them only as a check that the method does no harm. GDELT serves as a scaling test, since Noether Embedding notes that it has far more time points than typical embedding dimensions.

Metrics are filtered MRR and Hits@1/3/10, broken down by forecast horizon. Cost is measured as the number of state updates, function evaluations and wall-clock time. We plot MRR against update count across $\tau$ for the adaptive grid and across bin width for fixed grids.

The first decisive check is synthetic. We generate a multi-relational event stream from a known process with long quiet regimes and planted bursts, where the ideal grid is known. The controller should recover burst locations, measured as boundary density against ground truth, and beat equal-count binning on a variant with high-volume but uninformative repeated events.

The second decisive check is the Pareto plot on ICEWS05-15. The adaptive grid's curve must lie above both the fixed-width curve and the equal-count curve. Being above only the fixed-width curve is not enough.

The third decisive check is horizon-stratified error. If adaptive striding during forecasting reduces compounding, the gap over fixed grids should grow with horizon. A constant gap would mean the benefit comes only from better grouping of the training history.