Skip to main content

Link Prediction

Link prediction ranks candidate node pairs using information available at a declared decision time. A high score is not a probability unless a calibrated probabilistic model establishes that interpretation, and a future recorded edge is not automatically a positive social outcome.

Prerequisites​

Complete motifs, triads, and local structure. Common-neighbor heuristics use the same local closure patterns but require a prediction protocol.

Learning goals​

  • Split events at a temporal cutoff before constructing graph features.
  • State the undirected, unweighted preconditions of Jaccard similarity.
  • Separate candidate generation, scoring, labels, and evaluation.
  • Explain why unobserved and missing relationships are not reliable negatives.

Analysis contract​

  • Graph type: an undirected unweighted simple training graph built only from valid, non-self events before the temporal cutoff 2026-10-03T00:00:00Z; direction, strength, and event multiplicity are intentionally discarded for Jaccard.
  • Normalization: Jaccard is common-neighbor count divided by the size of the neighbor union and lies in [0,1][0,1] when defined.
  • Disconnected case: pairs in separate components have no common neighbors and score zero; zero means no support from this feature, not impossible linkage.
  • Interpretation limit: similarity is evidence, not a calibrated probability, future truth, recommendation, affinity, or causality.

Split before features​

The two October 3 valid events form the holdout. The training graph, candidate set, degrees, and neighbor sets use only earlier events. Building the graph from all events and merely hiding the labels afterward would cause time leakage: future edges could create the very common neighbors used to predict them.

The fixture's m01 row has no recorded target. It cannot be assigned a node pair or silently labeled negative. More generally, absent edges mix true non-events with unobserved, impossible, or censored pairs. A deployment evaluation also needs a declared candidate universe and ranking metrics appropriate to severe class imbalance.

Worked example​

import csv
from pathlib import Path

import networkx as nx

fixture = Path("tests/fixtures/graph-data-science")
with (fixture / "interaction-nodes.csv").open(encoding="utf-8") as handle:
node_ids = [row["node_id"] for row in csv.DictReader(handle)]
with (fixture / "interaction-relationships.csv").open(encoding="utf-8") as handle:
all_rows = list(csv.DictReader(handle))

cutoff = "2026-10-03T00:00:00Z"
valid = [row for row in all_rows if row["record_status"] == "valid"]
train_rows = [row for row in valid if row["observed_at"] < cutoff]
holdout_rows = [row for row in valid if row["observed_at"] >= cutoff]
train = nx.Graph()
train.add_nodes_from(node_ids)
train.add_edges_from(
(row["source"], row["target"])
for row in train_rows
if row["source"] != row["target"]
)
holdout_pairs = {frozenset((row["source"], row["target"])) for row in holdout_rows}
candidates = [("ada", "fox"), ("ben", "fox"), ("cy", "eli")]
scored = [
(u, v, round(score, 3), frozenset((u, v)) in holdout_pairs)
for u, v, score in nx.jaccard_coefficient(train, candidates)
]
scored.sort(key=lambda row: (-row[2], row[0], row[1]))
missing_excluded = all(row["record_status"] != "missing" for row in train_rows + holdout_rows)
print(f"cutoff={cutoff} train_edges={train.number_of_edges()} holdout_edges={len(holdout_rows)}")
print(f"scores={scored}")
print(f"missing_target_excluded={missing_excluded}")

Expected output:

cutoff=2026-10-03T00:00:00Z train_edges=5 holdout_edges=2
scores=[('cy', 'eli', 0.333, False), ('ada', 'fox', 0.0, True), ('ben', 'fox', 0.0, True)]
missing_target_excluded=True

This tiny counterexample is intentionally humbling: the highest Jaccard score is not a holdout edge, while both holdout edges score zero.

Limitations​

  • NetworkX's Jaccard implementation expects an undirected graph and ignores direction and timestamps once the training graph is built.
  • Common-neighbor scores favor graph regions with observable local closure and may disadvantage new or sparsely observed nodes.
  • Treating every non-edge as negative creates label noise and exposure bias.
  • A valid offline ranking cannot establish intervention effects; online tests need safety, consent, and causal design.

Practice​

Calculate precision at two for the three displayed candidates, including your tie-breaking rule. Then explain why this micro-fixture result is a code check rather than a performance estimate.

Next steps​

Continue to temporal and evolving networks to preserve event order inside reachability rather than only at the train–holdout boundary.

Primary sources​

Checked 2026-10-18: NetworkX, link-prediction reference; NetworkX, jaccard_coefficient; D. Liben-Nowell and J. Kleinberg, The link prediction problem for social networks.