Link prediction evaluation: time splits and honest negative candidates

Last updated: 5 Oct 20265 min read

tutorial

A link-prediction test ranks future valid relationships against eligible alternatives under a past graph snapshot.

Define the target edge

Predicting a learner’s next completed lesson differs from predicting any future click or a missing prerequisite in the catalog. Fix the edge type, horizon and eligible candidate set. A learner cannot complete an unpublished lesson, so that path should not enter the negative pool. Temporal recommendation evaluation has the same catalog-state constraint.

Split by time

Build training graph edges before a cutoff and reserve later edges as outcomes. For every historical decision, reconstruct node features and neighbors known then. Randomly moving existing edges into a test set can leave later edges in the training graph and turn a future-only relationship into a feature. Keep one final period untouched during model selection.

Treat unknown carefully

An unobserved learner-lesson pair is not always a true negative; the learner may never have seen the lesson. Negative sampling defines an evaluation comparison, not ground truth for every absent edge. Record sampling method and exposure eligibility. A model can win against easy random negatives yet fail to rank among realistic competing lessons.

Exercise candidates

At a historical cutoff, create one future positive lesson, one eligible but unchosen lesson and one unpublished lesson. Only the first two can enter the candidate comparison. Verify that the positive edge is absent from the input graph and that a later completion by another learner does not leak into earlier node features.

Implementation

def eligible_link_candidates(candidate_paths, published_at_cutoff, completed_paths):
    return [path for path in candidate_paths
            if path in published_at_cutoff and path not in completed_paths]

Performance and operating cost

Filtering C candidates costs O(C) expected time with set membership. Reconstructing graph snapshots and scoring K candidates can dominate; cache immutable snapshot IDs but include publication and exposure policy in the cache key.

Common Mistakes

Do not treat every absent edge as a confirmed negative preference.
Do not leave the target edge in the feature graph.
Do not evaluate against items unavailable at the decision time.