- 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., ) 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
-
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.
-
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?
-
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.
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} on all seven benchmarks (5 seeds). The d=1 dip (paired t-test) is significant on 3/7 at L=1, 6/7 at the standard L=2, 4/7 at L=3, 1/7 at L=4. Depth reshapes both the magnitude and the location: on PubMed the dip deepens monotonically (−3.8→−11.8→−12.0→−14.1 pp), while on Amazon-Computers the deficit moves to the far strata as the receptive field grows (d≥4 coverage 0.74→0.70→0.65 for L=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-L message-passing network, a node's representation is a function of its L-hop neighborhood only; so training-node features, and the containment that drives the shadow, can reach only nodes within L hops of supervision. Two consequences:
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≥ empty-rate. Empirically (Table 16) the empty-set term is the majority of the d=1 gap where empty sets concentrate near supervision (Coauthor, 12.5--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% at d=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−4); the tuned arm sweeps 16 configurations (learning rate ∈{0.01,0.005}, weight decay ∈{5e−4,0}, dropout ∈{0.5,0.2}, width ∈{64,256}; ≤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.