The Training-Set Shadow: How Message Passing Breaks Conformal Coverage on Graphs

Machine-learning models on graphs are often deployed with a reliability promise attached: conformal prediction gives each node a set of candidate labels that contains the true label a chosen fraction of the time, say 90%. We show this promise, while true on average, fails in a systematic and invisible way. Across seven standard benchmarks with few labeled nodes, the nodes sitting next to the training examples are the ones most often shortchanged, covered as little as 78% of the time under the most widely used scoring rule (adaptive prediction sets), even though the model classifies them more accurately than the rest of the graph, while faraway nodes receive more coverage than they need. A core of this failure persists under every scoring rule wherever the model makes confident mistakes, and the effect reappears, smaller, at much larger scale on a public citation network of over 160,000 nodes. We call this blind spot the training-set shadow, and we show how to see it: report coverage as a function of each node's distance to the training set, a profile whose one-number summary we call the shadow gap and which costs one graph traversal plus a labeled holdout to compute. Controlled experiments pin the cause on message passing, the mechanism by which graph neural networks blend each node's features with its neighbors': a feature-only model on identical data shows no shadow, moving the training nodes moves the shadow with them, and the effect switches on the moment a single round of propagation is added. We prove where the leak lives: near the training set, the network's representations contain copies of the very examples it was trained on, exactly for linear networks and in the infinite-width limit for nonlinear ones, where the resulting kernel reproduces the shadow with no training at all; that this containment inflates confidence is established experimentally. The repair is simple and carries a finite-sample proof: calibrate separately within each band of distance to the training set, which restores the target coverage in every band at a small cost in prediction-set size, whereas calibrating on other graph structure such as communities, though exactly valid on its own terms, leaves the shadow untouched. Practitioners should report the coverage-by-distance profile alongside the marginal average, and calibrate by position, not only globally.