Learning Time Boundaries via Historical Negative Sampling

59 concepts38 papers1 proposal

When machine learning models process dynamic data—such as evolving social networks, streaming news, or temporal knowledge graphs—they frequently suffer from a subtle form of cheating known as temporal blindness.

Consider a dynamic link prediction model tasked with forecasting whether two users will interact today. If we evaluate this model using standard random negative sampling, we pair a real interaction with a random pair of nodes that have never interacted in the history of the network. To achieve near-perfect accuracy on this task, the model does not need to understand when interactions happen; it only needs to learn who generally interacts with whom. It exploits static structural shortcuts, such as common neighbor counts, while remaining completely oblivious to time.

To expose this flaw, Poursafaei et al. introduced a simple memorization baseline called EdgeBank in Towards Better Evaluation for Dynamic Link Prediction. EdgeBank merely predicts that an edge will occur if it has been seen in the past. Surprisingly, this "dumb" baseline frequently outperforms state-of-the-art dynamic graph models, revealing that reported high performances are often an artifact of overly simplistic evaluation protocols.

The solution to this problem is historical negative sampling (and its broader counterpart, temporal contrastive learning). Instead of drawing negative samples from impossible or random pairs, this paradigm constructs negative examples from facts, links, or contexts that were completely valid in the past but are invalid at the current moment. By forcing models to distinguish between a true current event and a stale historical fact, we compel them to learn the precise boundaries of time.


The Anatomy of a Historical Negative

To understand why historical negative sampling works, we must look at how it alters the optimization landscape across different domains.

Standard Negative Sampling:
Anchor: (User A, interacts_with, User B) at t=Today
Negative: (User X, interacts_with, User Y) [Nodes that never interact]
-> Shortcut: Model just learns that User X and User Y are unrelated.

Historical Negative Sampling:
Anchor: (User A, interacts_with, User B) at t=Today
Negative: (User A, interacts_with, User C) at t=Today [Where A and C interacted frequently last week, but not today]
-> Challenge: Model must learn the exact temporal expiration of the A-C relationship.

In dynamic networks, as shown in the Temporal Graph Benchmark for Machine Learning on Temporal Graphs, historical negatives are edges that existed previously but are currently dormant. As Jiang et al. demonstrate in Exploring Time Granularity on Temporal Graphs for Dynamic Link Prediction in Real-world Networks, evaluating models against these dormant links prevents them from relying on static topology. If a model is penalized for predicting a link that was active yesterday but is inactive today, it must actively track the network's temporal dynamics.

This principle translates directly to Temporal Knowledge Graphs (TKGs), where facts have explicit timestamps or durations (e.g., (Barack Obama, holds_office, President of US, 2009-2017)). As noted by Cai et al. in Temporal Knowledge Graph Completion: A Survey, standard random corruption of these tuples fails to provide nuanced temporal boundaries. If the model only sees negatives where the entity is replaced by a random object, it learns semantic relevance but ignores event durations.


Forcing Geometric and Logical Boundaries

How do models mathematically ingest these harder negatives to build better representations?

1. Projecting onto Time-Specific Spaces

In HyTE: Hyperplane-based Temporally aware Knowledge Graph Embedding, Dasgupta et al. handle evolving facts by projecting entity and relation embeddings onto time-specific hyperplanes. During training, the authors select negative samples that are factually true at other time steps but invalid for the current temporal snapshot. This optimization forces the model to decouple an entity's general semantic meaning from its temporary state, carving out sharp chronological boundaries in the embedding space.

2. Disentangling Context from Timing in Language

Large Language Models often suffer from a similar issue: keyword matching shortcuts. If asked "Who was the president in 1990?", an LLM might answer with a president from 2010 simply because the words "president" and the entity name co-occur frequently in its pre-training corpus.

To fix this, Son developed a training strategy in Time-Aware Representation Learning for Time-Sensitive Question Answering that presents models with four distinct permutations of context and time:

  • Both context and time are correct.
  • Only context is correct (historical negative).
  • Only time is correct.
  • Both are incorrect.

By contrasting the true answer against a historical negative where the topical context matches but the time constraint is violated, the model learns to verify semantic relevance and temporal validity simultaneously. Similarly, Shang et al. show in Improving Time Sensitivity for Question Answering over Temporal Knowledge Graphs that substituting antonymous prepositions (such as changing before to after) as negative samples forces the model to learn the logical directionality of time.

3. Continuous Temporal Gradients in Time Series

In continuous domains like multivariate time series, treating negative sampling as a binary choice can introduce harmful false negatives. Because physical systems change slowly or exhibit periodic patterns, a segment sampled from a few minutes ago might be semantically identical to the current anchor.

To address this, Dang et al. introduced StatioCL: Contrastive Learning for Time Series via Non-Stationary and Temporal Contrast, which replaces binary negative classification with a continuous weighting gradient based on temporal distance. This is echoed by Li et al. in A time–frequency contrastive learning model for anomaly detection in multivariate time series, where a temporal-decay mechanism adjusts the penalty of negative samples. Samples closer in time are penalized less, respecting the natural flow and local dependencies of the data.


Respecting Real-World Lifecycles

Beyond fixing evaluation metrics, historical negative sampling is critical for aligning models with real-world constraints, such as item lifecycles and physical constraints.

In news recommendation systems, items are highly ephemeral. Bae et al. argue in LANCER: A Lifetime-Aware News Recommender System that models should select negative samples exclusively from items that were active during the exact same temporal window as the positive interaction. This ensures the model learns from realistic competition between items available at that time.

Similarly, in search and recommendation frameworks like IntSR, developed by Yan et al. in IntSR: An Integrated Generative Framework for Search and Recommendation, negative samples are strictly aligned with the historical availability of the corpus. Preventing the model from using items that did not yet exist as negative examples ensures that gradient updates are grounded in valid historical contexts.

In physical sensing applications, temporal alignment prevents optimization conflicts. For instance, in Contrastive Learning for Unsupervised Radar Place Recognition, Gadd et al. enforce a strict temporal buffer between anchor scans and negative samples. Because successive radar scans are highly correlated, an unbuffered negative sample could easily be a false negative representing the exact same physical location. Enforcing a temporal exclusion window—a concept also leveraged by Zhan et al. in traffic forecasting (STGL: Self-Supervised Spatio-Temporal Graph Learning for Traffic Forecasting) and Deldari in change-point detection (Time Series Change Point Detection with Self-Supervised Contrastive Predictive Coding)—ensures that the model does not try to push apart embeddings that represent the same underlying state.


Summary

Historical negative sampling shifts the focus of representation learning from broad semantic similarity to precise temporal alignment. By constructing negative samples from historical facts that have expired, or by enforcing temporal buffers and decay gradients, these techniques prevent models from taking static shortcuts. The result is a representation space that respects not just what an event is, but exactly when it matters.

Key Foundational Work

HyTE: Hyperplane-based Temporally aware Knowledge Graph Embedding (2018) — contributed 2 concept elements to this direction.
Timespan-Aware Dynamic Knowledge Graph Embedding by Incorporating Temporal Evolution (2020) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_historical_negative_sampling_81931250,
  title = {historical negative sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/historical-negative-sampling/rdr_81931250f9104507afcc5244e44bce44},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_historical_negative_sampling_81931250_v1,
  title = {historical negative sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/historical-negative-sampling/rdr_81931250f9104507afcc5244e44bce44/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake