How do you sample negative edges to train a link-prediction GNN on a very sparse graph?

## Why negatives have to be invented at all A graph gives you positives — the observed edges — and nothing else. The label set for a binary edge classifier has to be completed with non-edges, and there are an enormous number of them: on `n` nodes there are about `n^2 / 2` possible undirected pairs. At 0.001% density with 100,000 nodes, that is roughly 5 billion candidate pairs holding only about 50,000 real edges. Every training step therefore involves a **choice of negative distribution**, and that choice is a modelling decision, not a detail. ## What goes wrong with uniform negatives Draw a pair uniformly at random and, with overwhelming probability, you get two nodes with no relationship of any kind: different regions of the graph, no common neighbours, often both low-degree because low-degree nodes dominate a heavy-tailed degree distribution. Consequences: - **The task is trivial.** Almost any encoder separates a genuine edge from a random pair after a few epochs. Training loss goes to nearly zero while the model has learned very little about the decision boundary you actually care about. - **Popularity becomes a sufficient statistic.** Positives touch high-degree nodes more often than uniform negatives do, simply because high-degree nodes appear in more edges. A model can score well by learning *is this node popular* rather than *do these two belong together*. - **Offline metrics lie.** AUC computed against one uniform negative per positive can sit near 1.0 while the model is useless at the real job, which is ranking a true edge above the hundreds of *plausible* candidates a production system will put in front of it. ## Degree-matched negatives The first correction is to sample negatives from a distribution whose endpoint degrees look like the positives'. Concretely, corrupt one endpoint of an observed edge by replacing it with a node drawn in proportion to degree (or to some power of degree), rather than uniformly. Now popularity no longer separates the two classes, and the encoder is forced to use structure and features. This is the cheapest large improvement available and should usually be the default. ## Hard negatives The second correction is to make the negatives genuinely plausible: pairs at graph distance two, pairs sharing several neighbours, or the current model's own highest-scoring non-edges. These sit near the decision boundary and produce the gradients that matter. Two cautions: - **False negatives.** Real graphs are incomplete — the drug interaction has not been tested, the citation exists but is not in the dump. A two-hop pair with many common neighbours is precisely the kind of pair that is *missing rather than absent*, so aggressive hard mining trains the model to reject exactly the edges you hope to discover. - **Collapse.** If every negative is maximally hard, the label noise from false negatives can dominate and training degrades. Mixing a proportion of easy or degree-matched negatives with a proportion of hard ones is the usual compromise. Whatever the strategy, **filter against the full known edge set** — train, validation and test — before accepting a sampled pair, using a hash set of edge keys. A negative that is actually a held-out positive corrupts both training and evaluation. ## Resample or fix? Resampling negatives each epoch exposes the model to far more of the non-edge space and acts as a mild regulariser; a fixed negative set makes runs exactly comparable and is the right choice for the *evaluation* split. The common setup is: resample during training, freeze the negatives used for validation and test. ## Ratio, and what it does to probabilities Training with one negative per positive means the model sees a world where half of all pairs are edges. The true base rate is around 1e-5. The learned scores will still *rank* candidates sensibly — uniform downsampling of negatives shifts the log-odds by a constant — but the probabilities themselves are inflated by orders of magnitude. If you need calibrated numbers (a threshold, an expected-cost decision, a probability shown to a chemist), apply the case-control correction: add `log(r)` to the logit, where `r` is the fraction of negatives you kept, or recalibrate on a sample drawn at the true rate. If you only need a ranked shortlist, the ratio matters less — but say so explicitly rather than by accident. Note that degree-matched and hard negatives are *not* uniform downsampling, so the simple constant-shift correction no longer holds exactly; with those, calibrate empirically on a held-out set drawn the way production will draw candidates. ## How to evaluate instead The honest evaluation mirrors deployment: for each held-out edge, score it against a realistic candidate set — every node, or every node passing whatever cheap filter production uses — and report where the true partner lands. Mean reciprocal rank and hits@k over that candidate set are far more informative than AUC against a single easy negative. ## The short version to say in an interview Negatives are a distribution you choose. Uniform is too easy and rewards popularity; degree-matched is the sane default; hard negatives sharpen the boundary at the cost of false negatives on an incomplete graph; filter against all known edges; and remember the sampling ratio makes your probabilities, not your rankings, wrong.