acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
conformal prediction, graph neural networks, uncertainty quantification, conditional coverage, calibration, message passing, semi-supervised node classification, distribution-free inference

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_oC8HOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper investigates a systematic limitation of marginal conformal coverage in graph neural networks (GNNs), which the authors call the training-set shadow. Specifically, they show that nodes close to the labeled training set can experience substantially lower coverage than the nominal target, despite often achieving higher classification accuracy than more distant nodes. The authors attribute this phenomenon to message passing, which propagates information from training nodes into neighboring representations and can lead to overconfident predictions.

The paper provides empirical evidence across several graph benchmarks, investigates the phenomenon through architectural controls and theoretical analyses, and proposes a diagnostic based on coverage as a function of distance to the training set. As a remedy, the authors introduce distance-based Mondrian conformal calibration, which provides finite-sample coverage guarantees within each distance stratum.

Critical strengths
  • Interesting and relevant research question. The paper provides a formal and empirical investigation of an intuitive but important limitation of marginal conformal coverage. Understanding how coverage varies across different regions of a graph is relevant for assessing the reliability of GNN predictions.

  • Good empirical investigation. The authors evaluate the phenomenon across multiple benchmarks and experimental settings, including different architectures, training-set configurations, and nonconformity scores. The empirical analysis provides substantial support for the existence of nonuniform coverage.

  • Combination of empirical and theoretical contributions. The paper attempts to explain the observed phenomenon through the relationship between message passing, training-node representations, and predictive confidence, rather than limiting itself to reporting empirical observations.

  • Practical diagnostic and remedy. Reporting coverage as a function of distance to the training set is a useful diagnostic that could complement standard marginal coverage evaluation. The proposed distance-based calibration procedure also offers a relatively simple way to address the observed disparities.

Critical weaknesses
  • Insufficient investigation of the role of GNN depth. My main concern is that the paper attributes the observed behavior broadly to message passing without sufficiently disentangling its effects from the number of message-passing layers. The main experiments use two-layer GCNs, yet the number of layers determines how far information from training nodes can propagate. In particular, the coverage decrease observed again at larger distances (e.g., �0��0�) raises questions about the interpretation of the coverage profile. Although the paper studies propagation steps in other architectures, a direct and systematic investigation of GCN depth is needed to support the proposed explanation and clarify how the shadow changes with the receptive field. Appendix I does not even seem to be mentioned in the main paper, and in there homophily is mentioned as the representative feature. However, homophily is a consequence of the task [1], and no assumptions about the task have been made to the best of my understanding. Therefore, the conclusion lacks clarity.

  • Incomplete discussion of coverage behavior at larger distances. The presentation focuses heavily on undercoverage at distance one and overcoverage at intermediate distances, while the decrease in coverage at larger distances receives comparatively less attention. This behavior is important for understanding the full coverage profile and should be discussed more prominently rather than being treated primarily as a secondary effect. Right now, the authors claims do not seem fully supported by evidence.

  • Limited clarity and accessibility. The manuscript is unnecessarily dense and difficult to follow in several places. The related work section is particularly compressed and does not adequately contextualize the paper within the existing literature. The technical setup and theoretical explanations also introduce substantial notation and terminology without sufficient guidance for readers who are not already familiar with graph conformal prediction. Several passages would benefit from more precise, straightforward explanations.

  • Unclear significance of some contributions. While the empirical observation is interesting, the fact that marginal coverage can conceal subgroup-level disparities is already inherent in the nature of marginal guarantees. Similarly, the disappearance of a graph-positional effect when message passing is removed may be relatively intuitive; therefore, the authors should better articulate which aspects of their findings are genuinely unexpected and constitute the central contribution.

  • Presentation and clarity. Despite its surface-level linguistic fluency, the manuscript often lacks semantic precision and coherence. The prose is frequently formulaic, unnecessarily verbose, and difficult to follow. The related work section is particularly compressed, while the technical setup and theoretical explanations would benefit from clearer exposition. Some experimental choices, such as the treatment of the validation set, are insufficiently explained. Moreover, certain results are not adequately connected to the main text (e.g., the GCN-depth analysis in Appendix I), and some cross-references appear to be broken. Overall, the manuscript would benefit from substantial improvements in clarity, organization, and accessibility. Presentation is largely the reason for my current evaluation.

Questions for authors
  1. How does the number of GCN layers affect the training-set shadow? Since the receptive field depends directly on the number of message-passing layers, could the authors provide a systematic depth ablation for standard GCNs? In particular, does the location or magnitude of the coverage dip change as the number of layers increases? I believe the paper requires a much more robust evaluation and experimental detail with respect to this aspect, which should be treated as one of the (five) controls.

  2. How should the decrease in coverage at larger distances be interpreted? The results suggest that coverage does not necessarily increase monotonically with distance from the training set. Could the authors explain this behavior more thoroughly and clarify its relationship to the proposed mechanism?

  3. Could the experimental protocol be explained more clearly? The role of the validation set and its treatment across the different experimental settings are difficult to follow. A more explicit description would improve accessibility and reproducibility. Similarly, a clearer discussion about hyper-parameters tried would be helpful.

1 comment
AuthorsOpenReview ↗

GCN-depth ablation, two propositions for the depth and large-distance questions, and the central claim

We thank the reviewer. We ran the systematic GCN-depth ablation requested, and we add two short propositions that answer the depth and larger-distance questions directly. All numbers come from released scripts. The ethics flag is addressed in a separate comment.

Q1. How does GCN depth affect the shadow? We swept depth L∈{1,2,3,4}L\in\{1,2,3,4\} on all seven benchmarks (5 seeds). The d=1d{=}1 dip (paired tt-test) is significant on 3/73/7 at L=1L{=}1, 6/76/7 at the standard L=2L{=}2, 4/74/7 at L=3L{=}3, 1/71/7 at L=4L{=}4. Depth reshapes both the magnitude and the location: on PubMed the dip deepens monotonically (−3.8→−11.8→−12.0→−14.1-3.8\to-11.8\to-12.0\to-14.1 pp), while on Amazon-Computers the deficit moves to the far strata as the receptive field grows (d≥4d{\ge}4 coverage 0.74→0.70→0.650.74\to0.70\to0.65 for L=2,3,4L{=}2,3,4). Read with the fixed-capacity APPNP control already in the paper (which dials propagation steps at constant parameters), this shows the effect is message passing, not an artifact of two layers. We add this as a new appendix and reference it from the main text.

Proposition A (receptive-field confinement). For a depth-LL message-passing network, a node's representation is a function of its LL-hop neighborhood only; so training-node features, and the containment that drives the shadow, can reach only nodes within LL hops of supervision. Two consequences:

  1. Depth sets the shadow's location (the containment band is d≤Ld\le L), matching the ablation.
  2. It separates two regimes: undercoverage at small d (≤L)d\ (\le L) is feature containment; the decrease at large d (≫L)d\ (\gg L) is outside that zone, a distinct parameter-level effect (the model underfits regions supervision never propagates to). The profile need not be monotone.

The confinement is of the input receptive field; the learned weights still depend on the whole training set, which is exactly why the far-distance behavior exists. The statement assumes nothing about the task, so homophily is a correlate, not a premise (addressing your point that homophily is task-dependent).

Proposition B (exact empty-set decomposition). At each distance stratum, miscoverage equals an empty-prediction-set term plus a non-empty-exclusion term, exactly. An empty set is a guaranteed miss, so 1−coverage≥1-\mathrm{coverage}\ge empty-rate. Empirically (Table 16) the empty-set term is the majority of the d=1d{=}1 gap where empty sets concentrate near supervision (Coauthor, 12.512.5--12.7%12.7\%), while the exclusion term dominates on citation graphs. Both propositions are elementary formalizations included for precision, not claimed as new machinery.

Q2. Coverage at larger distances. Proposition A gives the interpretation you asked for: the far-distance decrease is not the containment shadow but underfitting outside the receptive field, so coverage is non-monotone because two mechanisms act in different distance regimes. We will foreground this rather than treat it as secondary, and report the full per-distance profile for every dataset.

Central contribution (which part is unexpected). The non-obvious finding is a direction reversal: the nodes nearest supervision are more accurate yet less covered (down to 78%78\% at d=1d{=}1). That marginal coverage can hide subgroup disparities is generic; that the best-predicted nodes are the worst-covered, that message passing causes it, and that a position-conditional recalibration repairs it exactly, is not. We will state this as the central claim.

Q3. Protocol (answered here; we will move this into the setup appendix). Validation set, by setting. The marginal and distance-Mondrian experiments use no validation set: the conformal quantile (one global, or one per distance stratum) comes from the calibration split only. Only the tuned models use a validation set, carved as a fixed held-out block from the pool before the calibration/test split, used solely for early stopping (patience 50) and model selection; it never touches calibration or test. The remaining pool is then split 50/50 into calibration and test. Hyperparameters. The main experiments use one fixed recipe with no tuning (2-layer GCN, width 64, 200 epochs, learning rate 0.01, weight decay 5e−45\mathrm{e}{-}4); the tuned arm sweeps 16 configurations (learning rate ∈{0.01,0.005}\in\{0.01,0.005\}, weight decay ∈{5e−4,0}\in\{5\mathrm{e}{-}4,0\}, dropout ∈{0.5,0.2}\in\{0.5,0.2\}, width ∈{64,256}\in\{64,256\}; ≤500\le 500 epochs, patience 50, selected by validation accuracy). We will also expand related work (graph conformal prediction: CF-GNN, DAPS, NAPS; conditional-coverage limits: Barber et al. 2021, Gibbs et al. 2025; label-position-bias and subgroup-generalization: Han et al. 2023, Ma et al. 2021), and fix the cross-references, adding a main-text pointer to the previously unreferenced supplementary-figures appendix (App. I, the mechanism figures) and the new depth appendix.

Reviewer_SoGbOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper identified inequality in terms of the coverage for node classification based on conformal prediction. In conformal prediction, a model is asked to provide a set of node labels that are plausible for the nodes given the network structure and node labels assigned to some nodes (training node labels). The training shadow, which the authors named, is a tendency that node classifiers based on message passing graph neural networks tend to have lower classification accuracy (in terms of the confirmal prediction) for nodes that are close to the training node labels.The authors showed that this tendency is consistent across different datasets and message passing graph neural networks, but where the shadow appears depends on the score used (noncoformity score).The authors attributed this training shadow to the "leakage" of the node labels, meaning that a node adjacent to training nodes receives the label that is the right label with a high probability and therefore the classifier becomes overconfidence for its prediction, leading to smaller candidate set, which causes the lower coverage.

Critical strengths

The critical strength of the paper is the identification of the association between the graph structure and coverage for conformal prediction. While it is trivial to anticipate that small candidate sets lead to lower coverage, the point that candidate sets tend to be small for the nodes adjacent to the tuning set is a useful insight into improvements for conformal prediction, as well as graph neural networks for neural classification.

Critical weaknesses
  1. The paper attributed the training shadow to the distance from the training label. The fact that training shadow appears next to the training nodes is a consequence not the cause, and the remedy only covers the consequential failures rather then the cause. More specifically, in conformal prediction, the coverage is largely determined by the candidate set size. Smaller candidate set size leads to lower coverage. In the paper, Table 14 shows this trend clearly (see the Accuracy and Coverage column). And a node has fewer candidates if the model assings most probabilities to fewer classes (skewed probability distribution over classes). And this skewed assignment of probabilities is what causes the training shadow and can be caused not only by the proximity to the training node labels but also for other factors. Thus, the author remedied one of many factors. In fact, Figure 5 showed that heterophily is also explaining the coverage dip. One can remedy the dip of the coverage by focusing on the cause, i.e., skewed probability distribution. Specifically, by stratifying the nodes by the p^\top rather than the distance. This does not require graph structure at all and can be computed easily, and addresses the training shadow due to heterophily and distance at the same time, since it remedies the cause, not the consequence. And this simpler remedy is still within Mondrian CP. If the distance-based stratification yields better correction than this naive Mondrian CP by probability distribution skewness (e.g., p^\top like Table 14), then it makes the claim of the paper stronger, i.e.., shadow appears more strongly than that anticipated by the skewness of the probability distribution. If this is the case, the paper can argue naturally the structual factors that need to be taken into account for addressing the converage inequality.

  2. The second weakness is about Table 2. Table 2 showed the coverage dip at distance 1 compared to the coverage of more distant nodes. My inspection of the table suggests that the stronger dip appears for d=3 and d=4, maning that only d=2 is not shadowed, consistently across different stratified samples. Calculating the average coverage for d=2, 3, 4 and compared against that for d=1, I find that coverage of d=1 is higher than the average coverage for all but the 2% stratified version. This results do not come along with the claim of the paper. This raises a question: is the reference used to compute the dip the right reference? Meaning that the dip is the difference between the converage at d=1 and that of the average of farther nodes. The average, however, is quantiied in two ways, unweighted and pooled. And depending on which average to use, we have contradicting results. It would be useful to show the results for both cases, and whether the shadow only appears near the training nodes or somewhere else in terms of the distance, since it is the main claim of the paper. On a related note, this table was presented only for OGBN-Arxiv. It would be extremely useful to show the same type of table for all datasets. Furthermore, because the coverage is determined largely by the size of the candidates, it would be useful to show the average candidate size at distance 1 and then 2, possibly shown in Table 1 and then Table 2.

Questions for authors
  1. Comparison against a naive Mandrian approach based on p^top. Does the distance-based stratification is better than simple

  2. What are the converage dip for d=1 compared to the two baselined (pooled and unweighted)? Did the shadow appear for other d?

5 comments
AuthorsOpenReview ↗

The p_top-Mondrian comparison you proposed, with both aggregations and set sizes

We thank the reviewer. We ran the comparison the reviewer proposed, and it meets the win condition stated in the review: distance-based stratification gives a better correction than a ptopp_{\text{top}}-Mondrian, which strengthens the claim. All numbers come from released scripts; the marginal and distance-Mondrian arms reproduce the paper's distance analysis.

W1 / Q1. Distance vs. ptopp_{\text{top}} stratification. We built the confidence-Mondrian you describe: equal-mass quantile strata in ptop=max⁡cPcp_{\text{top}}=\max_c P_c (no graph structure), compared head-to-head with distance-Mondrian. Near (d=1d{=}1) minus far coverage gap, pp, pooled (negative = d=1d{=}1 undercovered):

datasetmarginaldistance-Mondrianptopp_{\text{top}}-Mondrian
Cora-4.7-0.7-4.4
CiteSeer-9.0-1.3-6.9
PubMed-12.4+0.9-10.1
Amazon-Photo-7.2+0.0-5.9
Amazon-Computers-7.2+0.2-4.8
Coauthor-CS-6.5+0.5-3.1
Coauthor-Physics-4.8-0.3-1.9

The ptopp_{\text{top}}-Mondrian leaves a residual d=1d{=}1 shadow on all seven datasets (1.9 to 10.1 pp); distance-Mondrian closes it on all seven. The comparison is fair to your proposal: the ptopp_{\text{top}} strata are equal-mass quantile bins (0 fallback) and are valid on their own axis (~90% per bin). Giving ptopp_{\text{top}}-Mondrian 1010 bins (2.5×2.5\times the four distance strata) still leaves −2.0-2.0 to −10.1-10.1 pp, so the result is not an artifact of matching bins to the evaluation axis.

On cause vs. consequence: confidence skew and position are correlated, so we tested your remedy directly rather than argue the mediation. Conditioning on confidence (the ptopp_{\text{top}}-Mondrian) does not repair the distance profile, while conditioning on position does. The same answers the heterophily point (Figure 5): if confidence skew were the common mediator of both the heterophily-driven and the distance-driven dip, the confidence-Mondrian would repair the distance profile; it does not (residual 1.91.9 to 10.110.1 pp, 7/7). So position-conditional coverage requires conditioning on position: confidence is not a substitute, and the structural axis is not reducible to the skew it shares with heterophily. We will state this as the direct test of the cause-vs-consequence question.

W2 / Q2. Both aggregations, all datasets, set sizes. We now report the near-far gap two ways for all seven datasets:

  • Pooled (node-weighted, what a deployment sees): a d=1d{=}1 shadow on 7/7.
  • Unweighted (macro): 6/7. The exception is Amazon-Computers (macro gap +1.8+1.8), whose far bin (d≥4d{\ge}4) is itself undercovered, so the profile is U-shaped and the unweighted far-average is pulled below d=1d{=}1. That is additional far-distance undercoverage, not an absence of the near shadow.

Coverage by distance (marginal), all datasets (answering "where is the shadow"):

datasetd=1d{=}1d=2d{=}2d=3d{=}3d≥4d{\ge}4
Cora88.493.492.693.2
CiteSeer83.792.692.892.7
PubMed77.988.289.891.0
Amazon-Photo85.993.095.6--
Amazon-Computers85.893.689.474.3
Coauthor-CS84.290.691.788.3
Coauthor-Physics85.287.590.492.7

d=1d{=}1 sits below the near strata on all seven datasets (the pooled shadow above); it is also the single lowest stratum on six of seven, the exception being Amazon-Computers, whose d≥4d{\ge}4 is lower still (74.3%74.3\%, the U-shape). We will expand Table 1 with this profile for all datasets. (d≥4d{\ge}4 is blank for Amazon-Photo because, on this dense graph, only 2626 of its 72507250 nodes lie 4+ hops from training, below our 20-node reporting threshold.)

Mean adaptive-prediction-set (APS) size is smaller at d=1d{=}1 than at d=2d{=}2 on all seven datasets (Cora 1.61 vs 2.11; PubMed 1.22 vs 1.39; Coauthor-CS 1.46 vs 1.99), so near nodes receive the smallest sets and the lowest coverage, as you note. These go into Tables 1 and 2.

On the OGBN-Arxiv table (the dip at d≥3d{\ge}3, with d=1d{=}1 above the far-average): that table is the tuned arxiv model, which Appendix N flags as the regime where the deficit relocates off d=1d{=}1. It is a disclosed boundary case. The seven standard benchmarks above (fixed two-layer graph convolutional network) show the d=1d{=}1 shadow directly under the pooled aggregation, and we will report the per-distance profile for all datasets under both aggregations.

Reviewer_SoGbOpenReview ↗

Clarification

Dear authors,

W1 / Q1. Distance vs.

Could you clarify what the table shows? What each value in each cell shows? It wasn't clear to me from the explanations, I'm afraid. Also, some words are not clear to me. For example, "The p-Mondrian leaves a residual shadow on all seven datasets." I'm struggling to understand what "leaves" and "residual" here mean precisely in this context. It would be helpful if the authors use more clear direct language.

W2 / Q2

Would it be possible to show me the table for the stratified data as in Table 2 in the current manuscript for head-to-head comparison? Also, one question about the tuning. The fact that tuning produces different shadow is worthwhile to know. What are the explanations of why? That explanation is critical as the training shadow is, based on Section N, conditional. That is a key boundary of the claim needs to be clarified and explained clearly.

AuthorsOpenReview ↗

Clarifications: how to read the table, the stratified profile, and why tuning moves the shadow

Thank you. We rewrite the answers, add the table you asked for, and explain the tuning.

1. What the comparison table shows. For each dataset we measure coverage: the fraction of test nodes whose prediction set contains the true label. We measure it twice, once for the d=1d{=}1 nodes (one hop from the training set) and once for the farther nodes. The number in each cell is the difference: [coverage of d=1d{=}1 nodes] minus [coverage of farther nodes], in percentage points. A negative number means the d=1d{=}1 nodes are covered less often than farther nodes. That under-coverage of d=1d{=}1 is what we call the shadow.

Each column uses a different way to choose the threshold:

  • marginal: one threshold for all nodes (the standard method).
  • distance: a separate threshold for each distance stratum (a group of nodes at the same hop distance).
  • confidence (4 or 10): a separate threshold for each confidence stratum, i.e. the method you proposed; 4 or 10 is the number of strata.

"Leaves a residual shadow" just means: after applying that method, the number is still negative, so d=1d{=}1 is still under-covered. In plain words, the method did not remove the shadow.

Worked example, Cora. With the standard method the gap is −4.7-4.7 (d=1d{=}1 is covered 4.74.7 points less often than farther nodes). After the distance method the gap is −0.7-0.7 (essentially gone). After the confidence method the gap is −4.4-4.4 (almost unchanged). So choosing thresholds by confidence did not fix the shadow; choosing them by distance did. The same holds on all seven datasets.

2. The same table as Table 2, for the standard datasets. Here is the head-to-head you asked for, in the columns of Table 2. The nn column is nd=1n_{d=1}, the number of d=1d{=}1 nodes (Table 2 lists training-set size, since its rows vary that; here rows are datasets). Coverage (%) is by hop distance; the dip is d=1d{=}1 minus the pooled farther nodes, meaning all farther nodes combined, the same convention as Table 2; Mond.\ range is the span of distance-Mondrian coverage across strata (standard GCN, APS, 55 seeds; all dips significant by a paired tt-test):

Datasetnd=1n_{d=1}d=1d{=}1d=2d{=}2d=3d{=}3d≥4d{\ge}4dip (pp)Mond.\ range
Cora20388.493.492.693.2−4.7±2.4-4.7{\pm}2.489.9–95.1
CiteSeer14183.792.692.892.7−9.0±2.5-9.0{\pm}2.590.5–92.6
PubMed14277.988.289.891.0−12.4±4.0-12.4{\pm}4.089.9–91.1
Amazon-Photo1,26185.993.095.6n/a−7.2±1.1-7.2{\pm}1.189.8–90.1
Amazon-Computers1,54185.893.689.474.3−7.3±0.9-7.3{\pm}0.990.2–96.5
Coauthor-CS1,08484.290.691.788.3−6.5±1.6-6.5{\pm}1.689.6–90.4
Coauthor-Physics55685.287.590.492.7−4.8±2.2-4.8{\pm}2.289.7–90.4

Compared with the ogbn-arxiv Table 2: under the pooled dip, all seven datasets show a significant d=1d{=}1 dip, and the Mond.\ range shows distance-Mondrian restores the low strata to about 90%90\% (over-covering a few small far strata, as the arxiv table notes). Amazon-Computers is the one U-shaped case: its d=1d{=}1 is below the pooled far-average (−7.3-7.3) and its d≥4d{\ge}4 is itself low (74.374.3), so coverage is lost at both ends. (d≥4d{\ge}4 is n/a for Amazon-Photo: only 2626 of 7,2507{,}250 nodes are 4+4{+} hops out, too few to report.) This is Table 23 in the revised PDF.

3. Why tuning moves the shadow, and the boundary of the claim. First, what tuning does. On ogbn-arxiv with a tuned recipe the d=1d{=}1 shadow goes away, but the under-coverage does not disappear: it moves to the far nodes (d≥4d{\ge}4 drops to 7878--80%80\%). So tuning relocates the failure; it does not remove it.

Why does it move? We compared the fixed and tuned models at d=1d{=}1. The tuned model is actually more confident, not less. What differs is how often each model produces an empty prediction set at d=1d{=}1. An empty set is a guaranteed miss. The fixed model produces one about 5×5\times more often (3.3%3.3\% vs 0.7%0.7\%), and that accounts for about two-thirds of the coverage difference. So the mechanism is not average confidence; it is how often the model is so peaked that even its top label is excluded. We do not derive why a given recipe produces more or fewer empty sets near training; that is an empirical, recipe-dependent fact, and it is what makes the shadow conditional.

The boundary, stated plainly. The d=1d{=}1 shadow appears when the model is overconfident right next to its training set, which is the usual case with few labels and a standard recipe. A different training recipe can shift where the failure sits. What does not depend on the recipe is the lesson we draw: conformal coverage on graphs is unequal by position, a marginal (average) audit cannot see it, and the remedy is to audit coverage by position and recalibrate by position. We state this boundary explicitly in Appendix N of the revised PDF.

Please let us know if this explains.

Reviewer_zTtCOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies conditional miscoverage hidden by valid marginal conformal prediction on graphs. Under sparse supervision, globally calibrated prediction sets can under-cover nodes one hop from the training set, despite relatively high classification accuracy there. The proposed audit reports coverage by distance to training nodes. Paired MLP controls, moved training masks, propagation sweeps, architecture comparisons, and kernel experiments investigate the mechanism. The theory links peaked predictions to score-dependent miscoverage and identifies structural containment of training-node features in linear and infinite-width graph models. Distance-Mondrian calibration uses separate thresholds for fixed distance strata, giving the standard finite-sample cellwise guarantee in the stated transductive setting. The experiments also document score dependence, training-recipe dependence, and cases where the worst coverage occurs farther from the training set.

Critical strengths
  1. An actionable diagnostic supported by complementary controls. The central finding concerns where a valid marginal guarantee allocates its errors, a practically meaningful distinction. The paired MLP comparison and the fixed-capacity input/output propagation sweeps provide useful evidence that propagation can induce the positional disparity. The moved-mask, degree-stratified, empty-set, and tuned-training studies probe plausible alternative explanations. Reporting the complete coverage-by-distance profile is an inexpensive and useful recommendation even when a one-hop shadow is absent.

  2. A well-matched repair with a clear validity argument in its core setting. Distance strata are fixed by (G,T)(G,T) before calibration/test assignment, so pure within-stratum split conformal admits the usual exchangeability argument. The community-conditioning comparison helps establish why the partition axis matters. The manuscript appropriately distinguishes the containment statements of Results 2/4 from a theorem proving confidence inflation, and explicitly treats the inductive experiment as empirical rather than guaranteed.

Critical weaknesses
  1. The global-fallback implementation has a guarantee gap. Algorithm 1, line 10, and Appendix J say that using the global threshold for sparse cells makes the guarantee revert to marginal coverage. Result 3 justifies pure cellwise calibration; it does not justify mixing cellwise thresholds for large cells with a global threshold used only on sparse cells. A rare high-score cell can remain uncovered by the global threshold while the other cells are separately calibrated near 1−α1-\alpha, removing the over-coverage that previously paid for the rare cell. The hybrid can therefore fail even overall marginal validity. An independent fixed-population diagnostic with distinct scores, uniform calibration splitting, α=0.1\alpha=0.1, 100 calibration nodes, and a 5-percent high-score cell gives about 0.8610.861 average hybrid coverage versus 0.9010.901 for the fully global rule. This is an independently constructed counterexample, not a rerun of the paper's benchmarks. The reported no-fallback results remain unaffected, but the deployed fallback and its guarantee statement require correction.

  2. The strongest causal and generality wording exceeds what is established. The controls support that propagation can cause the effect, but the algebraic feature-containment results do not identify when that containment necessarily inflates confidence or produces undercoverage. The manuscript acknowledges this gap. It also reports that the tuned ogbn-arxiv model has no one-hop shadow (Appendix N), the exact Amazon-Photo kernel has no such dip (Table 11), and the no-empty APS variant largely removes the Coauthor shadows (Table 16). These are informative boundary cases, but they make broad claims about message passing breaking coverage too strong unless explicitly restricted to positional conditional coverage and the relevant confidence/score/training regimes. The phenomenon and audit remain valuable without a universal failure claim.

Questions for authors
  1. Clarification: validity of the hybrid fallback rule. What guarantee applies when Algorithm 1 uses cellwise thresholds for sufficiently populated strata but the global threshold only for sparse strata? Result 3 establishes validity for pure cellwise calibration, whereas this hybrid can remove the over-coverage of large strata that compensates for undercoverage of a rare stratum. Please justify the claimed marginal fallback guarantee or revise that statement.

  2. Evidence request: a guarantee-preserving sparse-cell implementation. For the sparse-calibration settings already examined in Appendix J, what coverage and set sizes result from using conservative within-cell quantiles, with an infinite threshold when the required order statistic does not exist? Alternatively, if cells are pooled, please specify when the partition is fixed and whether the guarantee concerns the pooled cells or the original distance strata. This would establish a deployable repair consistent with the stated theorem.

  3. Clarification: explaining the tuned-model boundary case. Appendix N reports that the tuned ogbn-arxiv model has no one-hop shadow despite similar overall accuracy. How do the fixed and tuned models differ in the d=1d=1 confidence distribution, confident-error rate, and randomized-APS empty-set frequency? These quantities could help explain when the proposed containment mechanism produces miscoverage and when it does not.

  4. Clarification: absolute undercoverage versus relative disparity. Table 16 shows that disallowing empty APS sets largely removes the Coauthor shadows, while deterministic APS can enlarge the relative dip through greater coverage of farther strata. For these decisive configurations, please distinguish absolute d=1d=1 undercoverage below 1−α1-\alpha from a negative d=1d=1-versus-farther coverage gap. How should the headline claim be scoped across scores, given that a relative gap need not imply a violation of the target coverage?

1 comment
AuthorsOpenReview ↗

Fallback guarantee corrected; diagnostics for the tuned-model and absolute-vs-relative questions

We thank the reviewer, especially for the fallback counterexample, which is correct. All numbers come from released scripts; the hybrid arm reproduces Appendix J at the stated split.

Q1. Validity of the hybrid fallback. We accept the premise. Using the global threshold on sparse strata is not justified by Result 3 (which covers pure cellwise calibration) and is not finite-sample valid. We will revise Algorithm 1 / Appendix J to state the hybrid as a heuristic rather than a guaranteed rule.

Q2. A guarantee-preserving sparse-cell implementation. Two facts.

(i) At the deployed protocol the fallback never fires. With the paper's four distance strata at the 50/5050/50 split, no stratum is sparse on any of the seven benchmarks, so hybrid, conservative-cellwise, and pooled calibration coincide. The reported distance-Mondrian results are then exact pure-cellwise calibration, and are unaffected.

(ii) Where sparsity bites (small calibration fraction or finer strata), the conservative within-cell quantile with q=+∞q=+\infty when ⌈(1−α)(n+1)⌉>n\lceil(1-\alpha)(n+1)\rceil>n (i.e. n≤8n\le 8 at α=0.1\alpha=0.1) restores per-stratum validity:

settinghybrid: worst-cov (size)conservative-∞\infty (size)full-set frac
Amazon-Photo, 4 strata, f=0.05f{=}0.0573.4% (2.04)85.9% (2.13)1.6%
PubMed, 8 strata, f=0.10f{=}0.1072.6% (1.53)81.5% (1.53)0.1%
Coauthor-CS, 8 strata, f=0.10f{=}0.1079.5% (1.90)87.6% (1.94)0.3%

Worst-stratum coverage recovers 77–1313 pp; the mean set size rises by under 0.10.1 label. Pooling also preserves validity, but on the pooled partition (fixed before calibration), and it can under-cover a heterogeneous merge (CiteSeer, 8 strata: pooled 80.2% vs conservative 88.5%). We therefore adopt the conservative-∞\infty rule in Algorithm 1.

Q3. Fixed vs. tuned ogbn-arxiv at d=1d{=}1, using adaptive prediction sets (APS) (5 seeds):

d=1d{=}1 quantityfixed (shadowed)tuned (no shadow)
mean ptopp_{\text{top}}0.710.84
confident-error rate (ptop ⁣≥ ⁣0.9p_{\text{top}}\!\ge\!0.9)0.0610.108
randomized-APS empty-set freq.0.0330.007
d=1d{=}1 coverage0.8790.917

We report these as measured. The tuned model is more confident, with a higher confident-error rate, yet shows no shadow. What tracks the coverage gap is the randomized-APS empty-set frequency: the fixed model emits about 5×5\times more empty sets at d=1d{=}1, and an empty set is a guaranteed miss, so this accounts for 2.72.7 pp of the 3.83.8 pp gap. The within-model overconfidence account is unchanged; the refinement (App. N) is that mean confidence does not separate the two models, the operative quantity being true-class exclusion / empty APS sets, already measured in Table 16.

Q4. Absolute undercoverage vs. relative disparity. From the APS-decomposition (Table 16), d=1d{=}1 coverage against the 1−α=0.901-\alpha=0.90 target:

datasetAPS (rand.)no-emptyempty$_{d1}$verdict under rand. APS
CiteSeer0.8370.8693%absolute (survives no-empty)
PubMed0.7790.8286%absolute (survives no-empty)
Coauthor-CS0.8420.96713%absolute under rand.; empty-set-driven
Amazon-Computers0.8580.8610.5%no d=1d{=}1 shadow (U-shaped)

Under randomized APS the shortfall is an absolute undercoverage below 1−α1-\alpha on six of seven benchmarks. On the Coauthor datasets the reviewer is right that it is empty-set-driven: disallowing empty sets lifts d=1d{=}1 coverage back above target (0.84 ⁣→ ⁣0.970.84\!\to\!0.97), so we will scope it as "absolute under randomized APS, relative under no-empty." On the citation graphs the undercoverage survives disallowing empties (CiteSeer 0.869, PubMed 0.828), i.e. a coverage violation from the confident-error channel; deterministic APS deepens it by d=1d{=}1 dropping further, not by far strata rising. Amazon-Computers has no d=1d{=}1 shadow (its deficit is at far strata). We will scope the headline to positional conditional coverage: absolute where the confident-error channel operates, and empty-set-driven on Coauthor, the same channel identified in Q3.

The two listed weaknesses. (W1) is the fallback gap, and Q1–Q2 above is the correction. We reproduce the construction (α=0.1\alpha=0.1, 100 calibration nodes, a 5% high-score cell: ≈0.861\approx 0.861 hybrid vs 0.9010.901 global), will mark the hybrid a heuristic and adopt conservative-∞\infty as the guaranteed rule. (W2) We will state the claim at the precision the experiments support: positional conditional coverage in the confident-error regime, a deficit we document across the sparse-label benchmarks, with a cheap audit and an exact fix. The boundary cases (tuned ogbn-arxiv, App. N; the exact Amazon-Photo kernel, Table 11; no-empty APS on Coauthor, Table 16) characterize when the effect occurs; they are part of the contribution, and we report them as such.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Response to the research-integrity flag

On the research-integrity flag. We respectfully but firmly disagree that this submission warrants an ethics flag raised by one of the reviewer, and we ask that it be reconsidered and withdrawn. The flag rests on a single inference: that because the reviewer found certain passages hard to follow, it is "unclear how the authors verified" the content. That inference does not hold. Difficulty in reading a passage is a presentation matter; it is not evidence of unverified or unaccountable content. An integrity flag is a serious instrument, and conflating it with a clarity critique is not appropriate.

The verification the flag questions was disclosed up front, in the submission's mandatory AI Use Statement. That statement is not a general disclaimer; it specifies exactly how each kind of content was checked, and the authors committed to it on the record at submission:

"The research questions, experimental designs, formal claims, and final conclusions of this work are the authors' own, and the authors take full responsibility for its entire content. ... All such output was checked by the authors: the proofs, which compose standard arguments (split-conformal exchangeability, Mondrian conditioning, and the ridge-regression smoother identity), were verified by hand; experiment code was reviewed for correctness before every run and every reported number was traced to its raw result file; the central empirical finding was independently reproduced by a separately written implementation; and all bibliography entries were verified against their sources."

This is precisely the accountability the flag questions, and it was stated before any review, not asserted after the fact. Concretely, it means:

  • Proofs: verified by hand; they compose standard, cited arguments, and we claim no new machinery.
  • Experiment code and numbers: reviewed for correctness before every run, and every reported number traced to its raw result file (the released scripts and result files let any reader reproduce each number).
  • Central finding: independently reproduced by a separately written implementation.
  • Bibliography: verified entry by entry against the primary sources.

Taken together, this is a reproducible submission in which a reader can regenerate every reported number from released code, and in which the proofs and citations were checked by the authors. That is the strongest available form of accountability for the content, and it is independent of the fluency of any individual sentence.

On the specific passages. If the reviewer will identify the passages they found ambiguous, we will clarify or rewrite them in the revision; we have already made a clarity pass and repaired cross-references, and we welcome making the exposition more accessible. But improving readability is a presentation improvement, distinct from, and not evidence against, the verification described above.

We take research integrity seriously, which is exactly why we are responding directly rather than letting the characterization stand. The verification process was documented at submission and is reproducible from the released artifacts. We believe the flag is not warranted and ask the Area Chair, Senior Area Chair, and Program Chairs to reconsider it. Thank You!

Dear Authors,

Thank you for your response. I acknowledge that the use of AI for drafting is permitted and that you have disclosed it in your AI Use Statement.

However, my concern goes beyond isolated clarity issues. The presence of so much AI-generated, difficult-to-follow text throughout the manuscript substantially undermines the paper's readability and makes it difficult to critically assess the scientific arguments. This is the reason why it raises concerns about the extent to which the generated content was carefully reviewed and validated by the authors, notwithstanding the verification procedures described in your statement.

While I appreciate your commitment to reproducibility, it does not fully address these concerns. I therefore maintain my research-integrity flag and leave its final assessment to the Area Chair.

Best regards.

AuthorsOpenReview ↗

Revised PDF uploaded: summary of changes by reviewer

Title: Revised PDF uploaded: summary of changes by reviewer

We are grateful to all three reviewers for the care they put into reading the paper and for feedback that improved it. zTtC's reading of the fallback statement caught a real overclaim; SoGb's proposed confidence-stratified comparison and request for a plainer, Table-2-format profile sharpened both the evidence and the exposition; oC8H's push on depth and on connecting the formal statements to the body led directly to the new ablation, the two added results, and a clearer narrative. We address each point in the revision below.

We have uploaded a revised PDF. The changes are (i) clarity improvements, (ii) one conceded correction to a guarantee statement, and (iii) new appendices integrating the experiments from our responses. No reported number or claim was changed, the submitted results are unaltered, and the added main-text page was used for clarity. Changes by reviewer:

Reviewer zTtC.

  • Fallback guarantee corrected. Algorithm 1 and Appendix J no longer state that the global-threshold fallback reverts to marginal validity. It is now described as a heuristic without a finite-sample guarantee (your counterexample, ≈0.861\approx 0.861 vs 0.9010.901, is cited), and the conservative within-cell rule, taking the full set when the (1−α)(1-\alpha) order statistic does not exist, is adopted in Algorithm 1 as the guaranteed option. Appendix J reports its coverage and set-size cost. The reported results are unaffected, since the fallback never fires at the stated protocol.
  • Tuned-model boundary (Appendix N). Now reports the fixed-vs-tuned ogbn-arxiv d=1d{=}1 diagnostics (confidence, confident-error rate, randomized-APS empty-set frequency) and attributes the boundary to the empty-set channel of the new Result 6, not to mean confidence.
  • Scope (Setup). A dip is now defined as a relative measure, with absolute undercoverage below 1−α1-\alpha named as a distinct quantity.

Reviewer SoGb.

  • New Appendix V. The confidence (p^top\hat p_{\mathrm{top}})-Mondrian comparison you proposed, at 44 and 1010 quantile strata (Table 22): it leaves a residual d=1d{=}1 shadow on 7/77/7 while distance-Mondrian closes it on 7/77/7. Mean set sizes at d=1d{=}1/d=2d{=}2 and both aggregations are included.
  • Full profile (Table 23). Coverage by distance for every dataset, not only ogbn-arxiv.

Reviewer oC8H.

  • New Appendix S. A systematic GCN-depth ablation, L∈{1,2,3,4}L\in\{1,2,3,4\} (Table 21 and figure), with overall accuracy to show oversmoothing.
  • New Results 5 and 6 (receptive-field confinement of the shadow; exact empty-set decomposition of positional miscoverage). These are the two propositions (A and B) from our response; the paper numbers all formal statements as "Result N", so they appear as Results 5 and 6. They answer how depth sets the shadow's location and how to read the larger-distance behavior.
  • Clarity. Related Work (Section 2) was rewritten to contextualize the paper against graph conformal prediction, conditional-coverage theory, and position effects in GNNs; the validation-set protocol and the hyperparameter grid are stated explicitly (Setup, Appendix N).
  • Central claim. The Introduction now states the unexpected finding directly: the nodes nearest supervision are the best-predicted ones yet the worst-covered.
  • Cross-references repaired. Every new result and appendix is now cited from the main text: the depth ablation (App. S), Results 5 and 6, and the distance-vs-confidence comparison (App. V), along with the previously unreferenced supplementary-figures appendix. No reference is broken.

The submitted version's numbers and claims are unchanged throughout; we are happy to provide a marked diff on request.

If any reviewer feels a point still needs more work, we welcome it and are ready to run further experiments or revise the text again during the discussion period. Our aim is to make this phase smooth and to leave the thesis stated as clearly as we can.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.