Why must held-out test edges be deleted from a GNN's message-passing graph, not just from its labels?
answer
- an edge plays two roles at once
- the label is sitting in the input
- one hop is enough to copy features
- remove both stored directions
- rebuild anything derived from the adjacency
basics
~20 sA single round of message passing copies each endpoint's features along the edge itself, so an edge left in the adjacency is read off rather than predicted. Delete held-out edges from the graph as well as the labels, and remove both stored directions.
solid answer
~50 sEdges play two roles in a link-prediction setup: they are the wiring the encoder passes messages over, and they are the supervision. If you split only the labels, the test edge is still in the adjacency, so during one round of aggregation node `u` receives `v`'s features and vice versa. The two endpoint vectors become mutually informative for the trivial reason that they were mixed along the very edge you are scoring, and test AUC climbs toward 1.0 while the model has no ability to find a genuinely unseen edge. The fix is a three-way edge split: the training-time graph contains only training message-passing edges, validation is scored on a graph of training edges, and test on training plus validation edges. In an undirected graph stored as two directed entries, both directions have to go — deleting one leaves the leak wide open.
go deeper
Remember that in link prediction an edge is both an input and a label, so a held-out edge has to disappear from the graph itself and not only from the label list.
Explain the mechanism: one aggregation round mixes the two endpoints' features along the edge being scored, and the edge also inflates both endpoints' degrees.
Show the full protocol you would run — three-way edge split, which graph is used at each stage, splitting training edges into message and supervision roles, rebuilding derived structures, and the diagnostics that expose a leak.
Own evaluation integrity as a standard: define the split protocol other teams reuse, insist on a structural baseline alongside every reported number, and require a temporal holdout wherever edges carry timestamps.
## Edges have two jobs In ordinary supervised learning the features and the labels are different objects, so a train/test split is unambiguous. In link prediction they are the same object. An edge is simultaneously: 1. **structure** — part of the adjacency the encoder aggregates over, and 2. **supervision** — a positive example the decoder is asked to score. Splitting only role (2) while leaving role (1) intact is the single most common evaluation bug in graph learning. ## The leak mechanism, concretely Suppose the edge `(u, v)` is held out for test but still present in the adjacency used at inference. One round of message passing updates each node from its neighbours: `h_u <- update(h_u, aggregate over neighbours of u)` Because `v` is a neighbour of `u`, `v`'s features flow into `h_u`; symmetrically `u`'s features flow into `h_v`. After a single round the two vectors share a component that exists *only because the edge exists*. The decoder does not need to infer anything: it detects the copied signature. With two or more rounds the effect compounds, and additionally the presence of the edge changes both endpoints' degrees, which many aggregations normalise by — another channel through which the answer bleeds in. The symptom is unmistakable once you know it: test AUC pinned near 1.0 from the first epochs, barely moving with model size or training time, and a model that nonetheless proposes garbage when asked for genuinely new edges. ## The correct protocol Split the **edges** (nodes normally stay put) into training, validation and test sets, then be explicit about which graph is used when: - **Training.** Message-passing graph = training edges only. Validation and test edges are absent entirely. Supervision = training edges as positives plus sampled non-edges. - **Validation.** Message-passing graph = training edges. Score the held-out validation edges against sampled negatives. - **Test.** Message-passing graph = training plus validation edges. Score the test edges. A refinement used in most careful implementations is to split the *training* edges again into a message-passing subset and a supervision subset, rotated between epochs. Otherwise every training positive is also visible in the graph, and the decoder learns a scoring rule that quietly relies on the edge already being there — a rule that has no meaning at inference, when the candidate pair is by definition unlinked. Training then mismatches deployment even though the test protocol is clean. ## Practical traps - **Undirected edges stored twice.** An undirected graph is usually materialised as two directed entries `(u, v)` and `(v, u)`. Removing one still leaves a path for messages to flow. Remove both. - **Cached or precomputed structures.** Normalised adjacency matrices, neighbour lists, random-walk corpora, precomputed shortest-path or common-neighbour features: anything derived from the graph must be rebuilt after the deletion, not reused from the full graph. - **Isolated nodes.** Deleting edges lowers degrees and can strand nodes with no neighbours at all. That is a legitimate consequence, but it changes what the encoder sees, so make sure the same graph is used consistently and that degree-zero nodes are handled rather than crashing the aggregation. - **Temporal graphs.** If edges have timestamps, a random edge split leaks the future into the past even when the adjacency is handled correctly. Split by time and build the message-passing graph from edges strictly before the cutoff. ## What is *not* leakage An important distinction to draw in an interview. After the held-out edge is removed, the model may still score the pair highly because `u` and `v` share several neighbours, sit in the same community, or have similar attributes. That is **signal, not leakage** — it is exactly the inductive bias link prediction is supposed to exploit. Leakage is specifically the case where information about the target edge's existence reaches the score through the graph itself. ## Diagnosing a suspected leak - Compare against a trivial structural baseline such as common-neighbour count on the same split. If the learned model is near-perfect while the baseline is mediocre, look harder at the split before celebrating. - Re-run the evaluation with the held-out edges definitively removed from every derived structure and see how far the metric falls. A collapse from 0.99 to 0.80 is the confession. - Check performance on a temporal holdout. Leak-free models degrade gracefully there; leaking models fall apart. ## The one-line answer The adjacency is an input, and a held-out edge left in it is the label pasted into the features. Split edges, rebuild every derived structure from the reduced graph, and delete both directions.
- Why also split the training edges into a message-passing subset and a supervision subset?Otherwise every training positive is visible in the graph while it is being scored, so the decoder learns a rule that depends on the edge already existing. At inference the candidate pair is unlinked by definition, so that rule does not transfer — training and deployment are solving different problems. Rotating which training edges carry messages and which carry supervision keeps the training task shaped like the real one.
- How would you spot this leak from the metrics alone, without reading the split code?Look for a test AUC pinned near 1.0 from the first few epochs, insensitive to model capacity or training length, alongside a simple common-neighbour baseline on the same split that scores far lower. Then re-evaluate on a temporal holdout. A clean model degrades gracefully there; a leaking one collapses, because a future edge genuinely is not in the graph.
- Is it leakage if the model still scores a removed test edge highly because its endpoints share five neighbours?No — that is the signal link prediction is meant to exploit. Leakage means information about the target edge's own existence reaches the score, through the adjacency or something derived from it. Shared neighbourhood, community membership and attribute similarity survive the deletion and are legitimate evidence. The line is whether the edge itself, in any cached form, is still visible.
It is like leaving the answer written on the desk during the exam: the student does not have to reason, only to read.
saying these in an interview costs you the question
- Removes test edges from the labels but leaves the adjacency intact
- Deletes only one direction of an undirected held-out edge
- Explains a 0.99 test AUC as evidence of a strong model
- Thinks one message-passing round is too shallow to leak
- Reuses a normalised adjacency built from the full graph