Graph Evaluation and Leakage
Graph observations are dependent. A random edge or node split can leave the test target encoded in training topology, neighbor features, normalization statistics, or pretrained embeddings. Evaluation starts by stating what is new at prediction time.
Prerequisites
Complete sampling and scaling large graphs. Sampling, preprocessing, and message passing must obey the same split boundary as labels.
Learning goals
- Distinguish transductive, inductive, temporal, and cross-graph evaluation.
- Identify target-edge, future-neighborhood, feature, and entity leakage.
- Define a negative candidate universe and ranking metric.
- Report named errors and structural slices, not one aggregate score.
Evaluation contract
- Question: rank three declared node pairs for an interaction first observed at or after
2026-10-03T00:00:00Z. - Setting: transductive; all seven node identities are declared before the cutoff, while future edges are hidden.
- Features: Jaccard overlap on valid, non-self, pre-cutoff interactions only; missing and malformed records are not negatives.
- Interpretation limit: offline discrimination measures association under this candidate policy, not intervention effects or future product value.
Split the whole pipeline
In a transductive node task, test nodes may participate in the training graph while their labels are hidden. In an inductive task, evaluation includes unseen nodes or graphs and requires features plus an encoder that can handle them. A temporal task permits only facts known by the prediction time. These settings are not interchangeable.
Remove held-out target edges before computing degrees, walks, embeddings, normalization, or message-passing neighborhoods. Fit imputers and scalers on training information. For link prediction, exclude true but unobserved relationships from claimed negatives where possible and document whether negatives are uniform, degree-matched, exposure-aware, or time-valid.
Accuracy over sampled balanced pairs is not a retrieval metric. Report the actual candidate policy and measures such as precision or recall at , ranking loss, calibration, and operational latency. Slice by degree, component, time, node novelty, and affected groups when those groups can be assessed safely.
Worked example
import csv
from collections import defaultdict
from pathlib import Path
cutoff = "2026-10-03T00:00:00Z"
fixture = Path("tests/fixtures/graph-data-science/interaction-relationships.csv")
with fixture.open(encoding="utf-8") as handle:
rows = [row for row in csv.DictReader(handle) if row["record_status"] == "valid"]
neighbors = defaultdict(set)
future = set()
for row in rows:
if row["source"] == row["target"]:
continue
pair = frozenset((row["source"], row["target"]))
if row["observed_at"] < cutoff:
neighbors[row["source"]].add(row["target"])
neighbors[row["target"]].add(row["source"])
else:
future.add(pair)
candidates = [("cy", "eli"), ("ada", "fox"), ("ben", "fox")]
scored = []
for left, right in candidates:
union = neighbors[left] | neighbors[right]
score = len(neighbors[left] & neighbors[right]) / len(union) if union else 0
scored.append((left, right, round(score, 3), frozenset((left, right)) in future))
print(f"cutoff={cutoff} setting=transductive")
print(f"scores={scored}")
print("future_features_used=False missing_records_used_as_negatives=False")
Expected output:
cutoff=2026-10-03T00:00:00Z setting=transductive
scores=[('cy', 'eli', 0.333, False), ('ada', 'fox', 0.0, True), ('ben', 'fox', 0.0, True)]
future_features_used=False missing_records_used_as_negatives=False
The high-scoring nonlink and zero-scoring future links are named errors worth inspecting; an aggregate alone would hide both failure modes.
Limitations
- The fixture is too small for uncertainty intervals, tuning, or generalization claims.
- Transductive results do not establish performance on unseen people or another network.
- Temporal order reduces one leakage route but does not repair collection bias or delayed observations.
- A sampled candidate set can make precision and class balance look unlike deployment.
Practice
Describe an inductive version in which Gia first appears after the cutoff. List which node features are available and why a lookup-table node embedding cannot represent the new identity without a fallback.
Next steps
Continue to fairness, privacy, and harm in networks before deciding whether a graph-learning task should be deployed at all.
Primary sources
Checked 2026-10-18: D. Liben-Nowell and J. Kleinberg, The Link Prediction Problem for Social Networks; W. L. Hamilton, R. Ying, and J. Leskovec, GraphSAGE; PyTorch Geometric, LinkNeighborLoader.