Link Prediction and Negative Sampling

Predicting whether an edge exists between two nodes is the task behind recommendation, knowledge graph completion and drug interaction prediction. It looks like binary classification and differs from it in ways that determine both how the model is trained and whether its reported performance means anything.

The negatives do not exist

A graph contains its edges. It does not contain labelled non-edges: an absent edge means either that the relationship does not hold or that it has not been observed. Training requires negatives, so they must be constructed, and how they are constructed is the main modelling decision.

Uniform random sampling picks node pairs at random. Simple, and almost every random pair is trivially separable, so the model learns to distinguish plausible from absurd rather than to rank plausible candidates. Performance on this looks excellent and does not transfer to the task, where the candidates are all plausible.

Degree-weighted sampling picks negatives in proportion to node degree, matching the popularity distribution of true edges so the model cannot rely on degree alone as a signal.

Hard negative mining selects pairs the model currently scores highly, which is where the useful gradient is. It produces much stronger models and risks selecting false negatives, real edges that were simply unobserved, and training the model to reject them.

Structural negatives, nodes two or three hops away rather than random, are plausible by construction and are the standard choice where a meaningful ranking is needed.

The negative distribution defines the task the model is trained for, which is why two papers reporting the same metric on the same dataset with different negative sampling are not comparable.

Evaluation leakage

Link prediction has a specific and pervasive leakage problem. Splitting edges into train and test, then computing node representations on the graph including test edges, lets the model see the answer through the structure. The split must remove test edges from the graph used for message passing, not only from the supervision.

Temporal graphs have a stronger requirement: the split must be by time, and the training graph must contain only edges that existed before the cutoff. Random edge splits on a temporal graph leak the future through structure and inflate results substantially.

When it breaks

Ranking metrics depend on the candidate set. Hits at \(k\) and mean reciprocal rank computed against 50 random negatives are not comparable to the same metrics against the full node set, and the first is far easier. The candidate construction belongs in any reported number.

Class imbalance is extreme. A graph with \(n\) nodes has \(O(n^2)\) possible edges and typically \(O(n)\) actual ones, so accuracy is meaningless and even AUC can be optimistic. Precision at \(k\) and MRR reflect the ranking use case better.

Cold-start nodes have no structure. A node with no edges has no neighbourhood to aggregate, so a pure structural model cannot embed it at all, which is exactly the case recommendation most needs. Node features are what make cold start tractable, and a purely structural approach has no answer.

Filtered ranking is standard in knowledge graphs and often omitted. When scoring a candidate, other true edges for the same query should be removed from the ranking, or the model is penalised for ranking correct answers highly. Unfiltered numbers are systematically lower and are not comparable to filtered ones.