Graph Tasks, Sampling, and Failure Modes

In link prediction, the graph lists observed edges. It does not list every true non-edge. An absent relationship may be impossible, merely unobserved, or likely to appear later. Negative sampling therefore shapes the task. Sample arbitrary node pairs and you get easy negatives and an overstated ranking score, while production candidates arrive from a much harder neighborhood or retrieval stage.

Large graphs add a second constraint. Full propagation may be infeasible when a node has millions of neighbors. Systems therefore sample neighbors, subgraphs, walks, or clusters. The sampling strategy changes which signals reach the model, and it can bias training toward high-degree nodes. Topology violates standard assumptions too. In heterophilous graphs, indiscriminate smoothing mixes deliberately different roles.

That failure was measured in 2020. Under heterophily, Zhu and colleagues report, “many popular GNNs fail to generalize to this setting, and are even outperformed by models that ignore the graph structure (e.g., multilayer perceptrons)”. Their repairs are ordinary. Separate a node's own embedding from its neighbors, use higher-order neighborhoods, combine intermediate representations. Together these “increase the accuracy of GNNs by up to 40% and 27% over models without them on synthetic and real networks with heterophily”, and the same designs “yield competitive performance under homophily”.

The point is not that graphs are unhelpful. It is that a model can be beaten by a network that never looks at an edge. An accuracy number alone will not tell you that is what happened.

The negative distribution should resemble the decisions the model will face. Published benchmarks fix that distribution explicitly rather than leaving it to the reader. The Open Graph Benchmark sets a different protocol for each dataset.

On ogbl-ppa, a graph of 576,289 nodes and 30,326,273 edges, the rule is uniform and shared: “we rank each positive edge in the validation/test set against 3,000,000 randomly-sampled negative edges, and count the ratio of positive edges that are ranked at the K-th place or above (Hits@K)”. Hits@100 is the number reported. On ogbl-citation2, 2,927,963 nodes and 30,561,187 edges, it is neither uniform nor shared: “Specifically, for each source paper, two of its references are randomly dropped, and we would like the model to rank the missing two references higher than 1,000 negative reference candidates.” Scoring is by MRR, and the split is temporal — papers published in 2019 supply the source papers for validation and test. Both protocols, and ogbl-citation2 itself, come from the extended 2021 paper and the benchmark's own documentation, not from the shorter 2020 proceedings version, whose predecessor dataset is called ogbl-citation. Three numbers separate the columns below: 3,000,000 shared random negatives, 1,000 candidates per positive, one time cutoff.

Uniform random pairs are cheap and simple, often too easy, and may quietly include unknown positives; they are a weak match for candidate ranking. Degree-aware or local negatives sample plausible pairs near the same nodes or in the same degree range: harder and more realistic, they control popularity shortcuts but need careful weighting, and they are the useful default in recommendation graphs. Temporal negatives take, at time t, only edges not yet observed under a valid future protocol; they match future-link prediction and avoid using future topology, but censoring remains a concern and they require timestamped graph snapshots.

That third column is not a refinement of the same task. Poursafaei and colleagues showed how far it moves the answer at NeurIPS 2022. They replaced random negatives with historical and inductive ones. On Wikipedia, CAWN's average precision fell from 0.99 to 0.89 to 0.86. EdgeBank, a pure memorization baseline with no learned parameters, fell too: the unlimited-memory variant EdgeBank-infinity from 0.90 to 0.50 and 0.48, the time-window variant EdgeBank-tw from 0.87 to 0.71 to 0.46. And yet: “EdgeBank is a surprisingly strong baseline for dynamic link prediction. In the historical NS setting, EdgeBank achieves the second best ranking amongst all methods.”

An independent re-implementation reproduced the inversion at NeurIPS 2023. Across thirteen datasets CAWN's average rank moves from 4.31 under random negatives to 7.54 under historical ones, while EdgeBank's moves from 7.54 to 5.92. The learned model and the lookup table trade places. Nothing about either model changed.

Graph errors concentrate around topology and around how the data was gathered. An accuracy column computed on a leaking benchmark will not reveal either.

The standard heterophily benchmarks leak. Platonov and colleagues audited them for ICLR 2023, and their abstract is blunt: “The most significant of these drawbacks is the presence of a large number of duplicate nodes in the datasets Squirrel and Chameleon, which leads to train-test data leakage.” The size of it: 2,978 of squirrel's 5,201 nodes are duplicates, and 1,387 of chameleon's 2,277. Split the accuracy on that line and the leak becomes visible. GraphSAGE scored 74.89% on chameleon's duplicate nodes against 46.17% on its non-duplicates. Removing the duplicates reordered the leaderboard: ResNet+adj fell from 71.07% to 38.67% on chameleon, and from 2nd to 12th place in the model ranking.

Years of reported progress on heterophily had been read off a single aggregate number that could not see any of this.

Sampling methods trade coverage, variance, memory, and systems complexity. The first of them arrived with its budget written down. GraphSAGE, published in 2017, fixes per-batch cost at O(prod of S_i) by drawing a bounded number of neighbors at each hop. The configuration was K=2 hops, with S1=25 neighbors at the first hop and S2=10 at the second. That is the whole reason a node with millions of neighbors is trainable at all — 25, then 10, whatever the real degree turns out to be.

The trade was measured rather than assumed. The second hop bought a 10-15% average accuracy gain over K=1. Going beyond K=2 returned only 0-5% more, for a 10-100x runtime increase. On the price paid for the bound, the authors are direct: “Thus, despite the higher variance induced by sub-sampling neighborhoods, GraphSAGE is still able to maintain strong predictive accuracy, while significantly improving the runtime.” The variance is not an artifact to be tuned away. It is the term the budget buys.

The other three families move the same trade elsewhere. Subgraph sampling trains on induced, random-walk, or clustered subgraphs. Precomputed propagation separates graph diffusion from a simpler trainable predictor. Partitioned or distributed execution places graph shards and communication across machines. Each one answers the same question: how much of the graph a single update is allowed to touch. Each answer carries a variance and a coverage profile of its own.

The routine separates representation failure from split and sampling artifacts.

1. Stratify by degree and component. Compare hubs, low-degree nodes, isolated nodes, and components. Degree comes first because the bias is structural rather than incidental. Subramonian and colleagues surveyed 38 degree-bias papers for NeurIPS 2024 and stated the result as a theorem: “We prove that high-degree test nodes tend to have a lower probability of misclassification regardless of how GNNs are trained.” They validate the account on 8 real-world networks. The recoverable size of the gap has been measured independently. GraphPatcher, at NeurIPS 2023, raised low-degree node performance by up to 6.5% and overall performance by up to 3.6% across seven benchmark datasets, by test-time augmentation alone. A single aggregate accuracy hides all of that.

2. Measure homophily and relation patterns. Check whether the architecture's smoothing assumptions fit the graph — and check the benchmark itself, since chameleon and squirrel carried 1,387 and 2,978 duplicate nodes before anyone looked.

3. Vary depth and sampling. Observe oversmoothing, variance, and neighborhood coverage, with GraphSAGE's own trade as the reference point: 25 then 10 neighbors, a 10-15% gain for the second hop, 0-5% for anything beyond it at 10-100x the runtime.

4. Rebuild temporal splits. Ensure all features and edges respect the prediction cutoff, in the way ogbl-citation2 does by handing papers published in 2019 to validation and test.

5. Challenge the negative sampler. Use harder, local, and production-like candidates. If a parameter-free memorization baseline such as EdgeBank takes the second best ranking amongst all methods once negatives are drawn from history, the leaderboard you have is partly a statement about your negatives.

6. Compare relational ablations. Remove or shuffle edges to quantify how much topology contributes. That is the ablation that would have caught a model outperformed by one ignoring the graph structure entirely.

Link-prediction evaluation depends on what an unobserved relationship represents. The three cases need three different protocols.

An impossible edge cannot exist under domain rules — an incompatible pair of entity types, for instance. It is safe to exclude from candidates and useful for schema validation. It should never be left in the pool, where it inflates the count of easy negatives without testing anything.

An unobserved edge may exist and simply has not been measured. It creates label uncertainty, requires careful negative sampling, and biases results toward well-observed nodes. An undiscovered fraud link is a negative in the file and a positive in the world. This is the case whose cost has been priced: on ogbl-citation2, one shared random negative set gives the best model an MRR a shade under 90, and 500 heuristic-sampled hard negatives per positive give slightly over 20.

A future edge is absent now and may appear later — a new buyer–seller interaction. It needs temporal evaluation, supports forecasting questions, and leaks easily through future topology. Two published protocols show the two halves of that. The Open Graph Benchmark handles the split by time, dropping two references per source paper and ranking them against 1,000 negative reference candidates, with 2019 papers reserved for validation and test. Poursafaei and colleagues handle the sampler, and on Wikipedia the move from random to historical to inductive negatives took CAWN's average precision from 0.99 to 0.89 to 0.86.

The negative set is a modeling decision with a published price tag, not a preprocessing detail. Say which of the three meanings your absent edges have, and the reader can tell what your metric measured.