acceptodds
Under review as a conference paper at ICLR 2027

Graph-Localized Coverage for Conformal Prediction on Inductive Graphs

Abstract

Conformal prediction (CP) provides marginal coverage guarantees, but marginal coverage does not determine where prediction errors occur on a graph. Queries from different graph neighborhoods can exhibit substantially different levels of uncertainty even when aggregate coverage remains near its target. We introduce GLocalCP, an online CP framework for inductive node classification and edge prediction that combines marginal and graph-local calibration with uncertainty-adaptive prediction sets. Specifically, GLocalCP puts forth a novel uncertainty-adaptive nonconformality score that relies on the mutual information obtained from Monte-Carlo (MC) dropout based prediction. Then, it augments a global online threshold with a kernel-based local correction that propagates coverage feedback among similar graph queries. On the theoretical horizon, we establish pathwise marginal calibration error without exchangeability or stationarity and, for the exact-kernel formulation, an explicit graph-localized calibration guarantee. Experiments on seven node-classification and seven edge-prediction benchmarks show that similar marginal coverage can conceal substantially different local reliability. Our proposed GLocalCP maintains coverage near the target while consistently reducing graph-local calibration error. Uncertainty scaling in GLocalCP further reduces prediction-set size across all evaluated node and edge datasets while leaving marginal coverage essentially unchanged.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
conformal prediction, graph learning, graph-local coverage

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_R1CEOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes GLocalCP, which is an online conformal prediction (CP) method for inductive node classification and edge prediction tasks where the graph is evolving. GLocalCP tries to address the issue of marginal coverage, where errors may not be uniform across the graph structure. GLocalCP augments prior work in online CP (i.e., adaptive conformal inference), which tracks errors to update a global conformal threshold, with an additional kernel-based local correction term that accounts for coverage errors between inputs with similar graph representations. GLocalCP also uses an additional uncertainty-aware scaling term for the non-conformity scores based on mutual information estimated using MC dropout to improve prediction set size. In addition to the methodological contributions, the paper provides theoretical guarantees for marginal coverage in this inductive setup (not requiring exchangeability or stationarity) as well as a graph-local calibration guarantee. Experiments were conducted on popular graph benchmark datasets and show improvement in graph-local calibration errors compared to other baseline methods.

Critical strengths
  • The paper is well-motivated, as it addresses an important limitation of marginal coverage, which is that it doesn't give a more granular assessment of where errors occur in the graph-query space. This is seen clearly in the edge prediction results, as the authors noted.

  • GLocalCP's design is quite intuitive and clever in how it incorporates the global threshold, graph-local calibration, and uncertainty scaling terms, and the experiments and ablation study are comprehensive.

  • The pathwise marginal guarantee is quite appealing as it allows for (supposedly arbitrary) sequential dependencies that would arise in the inductive graph setting.

Critical weaknesses
  • The overall presentation (particularly starting at Section 3.2 onwards) is not fully clear. It's not clear from the main paper whether the inductive task is fixed a priori (i.e., node classification or edge prediction), with GLocalCP being run on task-specific streams (i.e., only new nodes for node classification and only new edges for edge prediction), or whether a single GLocalCP stream is intended to support a heterogeneous stream of node/edge updates. The experimental results seem to evaluate the tasks separately, but the problem statement and Algorithm 1 do not make it very clear. This distinction also matters in understanding whether the (qn,gn)(q_n, g_n) state is shared or not between update types.

  • The paper cites but does not compare against [1], which is a very relevant prior conformal prediction method designed for inductive graphs under the arrival of new nodes/edges. Given the overlap with this paper's setting, a comparison against [2], or a clear explanation of why the experimental protocols are incompatible, is necessary.

  • The theoretical graph-local criterion is defined over a supremum of the representation space, whereas the "worst-case" KK is computed as the maximum of a finite set (6464) of "anchor" points. It would be nice to see a wider range of the number of anchor points (e.g., 256-1024) to understand any sensitivity in estimating the actual "worst-case" metric.

[1] Soroush H. Zargarbashi and Aleksandar Bojchevski. Conformal inductive graph neural networks, ICLR 2024

Questions for authors

(See weaknesses)

  • Is the prediction task fixed before GLocalCP is run, meaning the stream of updates includes only node or edge updates exclusively?

  • How does GLocalCP compare against [1]?

  • How does this method relate to this recent paper [2], which explores the use of localized CP to address the issues with marginal coverage in the transductive setting?

  • What were the marginal coverages (and prediction set sizes) like for the Global MI ablation compared to GLocalCP? Since gng_n is used to construct the prediction set, removing it would materially change the prediction sets as well as possibly affect any finite-sample dynamics. Reporting these numbers would also reinforce the distinction between qnq_n and gng_n as global and local calibrators.

[1] Soroush H. Zargarbashi and Aleksandar Bojchevski. Conformal inductive graph neural networks, ICLR 2024

[2] Baghershahi et al., GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs

4 comments
AuthorsOpenReview ↗

Response to Reviewer R1CE (1/2): task setup, comparison with [1], relation to GraphLCP

We thank the reviewer for the careful reading and the positive comments on the motivation and design. All results are means over 50 seeds.

Q1 / W1. Task setup: one fixed task per stream

The task is fixed in advance, and node classification and edge prediction are run as separate streams: a node stream contains only arriving nodes, and an edge stream contains only candidate edges. Each run maintains its own state (qn,gn)(q_n,g_n), and no state is shared between the two tasks. We agree that the problem statement and Algorithm 1 did not make this explicit. The problem formulation (Sec. 2) will state: "The prediction task (node classification or edge prediction) is fixed in advance; each task is run on its own stream and maintains its own state (qn,gn)(q_n,g_n)." Algorithm 1 will take the task and its query representation as inputs.

Q2 / W2. Comparison with [1] (Zargarbashi & Bojchevski, ICLR 2024)

We have added the comparison. [1] addresses inductive node classification: NodeEx CP and EdgeEx CP differ in how the graph grows (by nodes or by edges), but both predict node labels. Our node streams add one node at a time, so we compare with NodeEx CP on the seven node streams under the same protocol; our edge task predicts whether a candidate edge exists, which [1] does not consider. The results for NodeEx CP are below; those of GLocalCP are in Table 1.

DatasetCovSizeKK
Cora0.9092.450.0325
CiteSeer0.8872.660.0320
PubMed0.8971.110.0337
Computers0.9091.280.0645
Roman-empire0.8993.350.0579
Amazon-ratings0.8943.250.0258
ogbn-arxiv0.8915.000.0321

NodeEx CP's coverage is close to the target but varies between 0.887 and 0.909, whereas GLocalCP stays at 0.900–0.902, because NodeEx CP relies on exchangeability while GLocalCP corrects its threshold from sequential coverage feedback. GLocalCP's gap KK is 3.2–39× smaller on every dataset (e.g., 0.0028 vs. 0.0321 on ogbn-arxiv). NodeEx CP returns smaller sets on all seven datasets. On Cora and Computers it does so at coverage 0.909, so it is the more efficient method there; on the other five its coverage is below the target (0.887–0.899).

We also added five online baselines that receive the same sequential feedback (ACI, conformal PID, OLCP, MVP and GCC). GLocalCP has the smallest KK on all 14 streams, 10–63× smaller than the best of them on edges; full tables are in our response to Reviewer UvUM (part 3/3).

Q3. Relation to GraphLCP [2]

GraphLCP and GLocalCP both aim to go beyond marginal coverage on graphs, but they study different problems. GraphLCP works in the transductive setting, on a fixed graph with an exchangeable held-out calibration set, and asks which calibration nodes are close to a test node; it answers with a structure-aware PageRank kernel that reweights calibration scores. GLocalCP works on inductive streams, where nodes and edges arrive over time and exchangeability no longer holds, and asks how to keep calibration valid and locally balanced as the graph evolves; it answers with sequential coverage feedback, which also yields a guarantee for local calibration and extends to edge prediction. The authors of [2] name dynamic graphs with evolving topologies as future work, which is the setting we study, so we view the two as complementary.

AuthorsOpenReview ↗

Response to Reviewer R1CE (2/2): audit anchors and the Global-MI ablation

W3. Supremum vs. a finite set of anchors

We extended the audit to 256, 512 and 1024 anchors drawn from the post-prefix stream, with nested sets (256⊂512⊂1024256 \subset 512 \subset 1024) and the same kernel; the default 64 anchors come from the calibration prefix. The table reports KK for GLocalCP, and for ACI and conformal PID at 1024 anchors.

TaskDatasetGLocalCP, 64 (default)GLocalCP, 256GLocalCP, 512GLocalCP, 1024ACI, 1024PID, 1024
EdgeCora0.00090.00110.00120.00120.04560.0312
EdgeCiteSeer0.00170.00210.00220.00230.06450.0520
EdgePubMed0.00030.00030.00030.00030.02530.0199
EdgeComputers0.00400.00440.00450.00470.04700.0449
EdgeRoman-empire0.00070.00110.00130.00140.04200.0235
EdgeAmazon-ratings0.00070.00070.00070.00080.02070.0157
Edgeogbn-arxiv0.00210.00250.00250.00260.02640.0294
NodeCora0.00890.01010.01070.01110.02220.0221
NodeCiteSeer0.00500.00570.00600.00610.01340.0126
NodePubMed0.00550.00610.00630.00650.02230.0225
NodeComputers0.01390.01540.01580.01600.06360.0635
NodeRoman-empire0.01790.01820.01830.01830.04760.0495
NodeAmazon-ratings0.00070.00080.00100.00110.00810.0081
Nodeogbn-arxiv0.00280.00310.00330.00340.01800.0195

The maximum over a finite anchor set is a lower estimate of the supremum, and with nested sets it can only increase as anchors are added; the question is by how much. From 256 to 1024 anchors, GLocalCP's KK increases by at most 0.0010 on nodes and 0.0003 on edges, and the default 64-anchor value differs from the 1024-anchor one by at most 0.0022 and 0.0007, so the default estimate is already close to the value obtained with sixteen times as many anchors. The comparison is also unchanged: at 1024 anchors GLocalCP has the smallest KK on all 14 streams, and the better of ACI and PID is 9.6–62× larger on edges and 2.0–7.6× larger on nodes. Sec. 5.1 will state that the reported KK is the maximum of EN(z)E_N(z) over 64 audit anchors and therefore approximates the supremum from below, and the table above will be added to the appendix.

Q4. Marginal coverage and set size of the Global-MI ablation

Global MI and GLocalCP are both at 0.900–0.902 on all 14 streams, so Global MI already attains the marginal target, and marginal calibration is enabled by the global state qnq_n. Marginal coverage alone does not make errors evenly distributed, however: as reported in Table 2a, the graph-local gap of Global MI is 1.8–9.5× larger than that of GLocalCP on nodes and 11–70× larger on edges (e.g., 0.0145 vs. 0.0028 on ogbn-arxiv nodes, 0.0386 vs. 0.0009 on Cora edges). This is why we introduce gng_n: we want a method that is calibrated both marginally and locally, with qnq_n and gng_n serving these two purposes respectively. Because GLocalCP additionally balances coverage across the representation space, its set sizes differ from those of Global MI, as the reviewer anticipated. On edges, sets are smaller on six of seven datasets, by 3.2–9.3% (e.g., Cora 1.719 → 1.559, CiteSeer 1.742 → 1.581), and 1.5% larger on ogbn-arxiv. On nodes they are essentially unchanged on four datasets (e.g., Cora 2.524 vs. 2.527, Amazon-ratings 3.331 vs. 3.347) and larger on Computers (1.333 → 1.473), Roman-empire (3.706 → 5.363) and ogbn-arxiv (7.272 → 10.563). The coverage and set size of Global MI on all 14 streams will be added to the component-ablation tables in the appendix, next to its KK, and referenced from the ablation table in the main text.

I thank the authors for their thorough rebuttal. All of my questions and concerns have been addressed and I have increased my score, accordingly.

AuthorsOpenReview ↗

Thanks to Reviewer R1CE for the positive feedback and the score increase to 3

We sincerely thank the reviewer for the careful reading of our response and for raising the score. We are glad that the additional results and clarifications addressed your questions and concerns. All the revisions and additional results discussed in the rebuttal will be incorporated into the revised paper.

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

This paper presents GLocalCP, an online conformal prediction framework for node classification and edge prediction on evolving inductive graphs. The method combines a global calibration threshold with a kernel-based local correction, allowing coverage feedback to be shared among graph queries with similar representations. It also uses mutual information estimated through MC dropout to adapt nonconformity scores according to predictive uncertainty. The authors establish pathwise marginal and graph-localized calibration guarantees under the stated assumptions, without requiring exchangeability or stationarity. Experiments on seven graph datasets show that GLocalCP maintains coverage close to the target level while reducing graph-local calibration error. Additional ablation studies examine the effects of local feedback and uncertainty scaling, as well as robustness across different GNN architectures, nonconformity scores, and edge-query distributions.

Critical strengths
  1. Meaningful problem formulation and a clear approach. The paper addresses an important issue in graph conformal prediction: achieving good overall coverage does not necessarily mean that predictions are equally reliable across different graph regions. The combination of global online calibration and kernel-based local feedback is intuitive and well motivated. I also appreciate that the framework applies to both node classification and edge prediction.
  2. Consistent experimental results and useful ablations. The experiments cover seven graph datasets and two prediction tasks, with consistent improvements in the reported graph-local calibration error. The ablation studies are particularly useful, as they show that local feedback is responsible for reducing calibration disparities, while uncertainty scaling helps reduce prediction-set size. The additional experiments with different GNN backbones, nonconformity scores, and edge-query distributions further support the effectiveness of the approach.
Critical weaknesses
  1. The connection between the theoretical guarantees and practical evaluation could be clearer. The theoretical analysis is a valuable part of the paper. However, Theorem 4.1 applies to the exact-kernel formulation, while the experiments use random Fourier features for scalability. The authors acknowledge this distinction, but it would be helpful to further understand how the approximation affects local calibration in practice. In addition, the reported local calibration metric is evaluated over 64 audit anchors. A sensitivity analysis using different numbers or selections of anchors would provide additional confidence in the reported improvements.
  2. More direct evaluation of temporal adaptation would strengthen the paper. The method is motivated partly by evolving graph streams and potential distribution shifts. However, most datasets use random node arrival orders, which may not fully reflect challenging temporal changes. Additional analysis under more explicit distribution shifts would help demonstrate how effectively GLocalCP adapts to changing graph-query distributions. I consider this an opportunity to strengthen the empirical validation rather than a fundamental limitation of the proposed approach.
Questions for authors
  1. Could the authors provide some additional analysis of how the random Fourier feature approximation affects graph-local calibration? In particular, I would be interested in whether the reported local calibration results are sensitive to the number and selection of audit anchors.
  2. Since the framework is designed for evolving graphs, could the authors further discuss or evaluate its behavior under more explicit temporal distribution shifts? For example, a sliding-window analysis of local coverage might help illustrate how quickly the method adapts when the query distribution changes.
  3. The MI-based uncertainty scaling improves prediction-set efficiency, but MC dropout requires multiple forward passes. Could the authors comment on the computational overhead and the trade-off between prediction-set size and inference cost?
3 comments
AuthorsOpenReview ↗

Response to Reviewer s6Sb (1/2): RFF approximation and audit anchors

We thank the reviewer for the constructive comments. All results are means over 50 seeds.

Q1 / W1. Effect of the RFF approximation and sensitivity to audit anchors

RFF vs. exact kernel. Theorem 4.1 is stated for the exact kernel. In our experiments, we approximate the kernel with random Fourier features (RFFs) to reduce computational cost. The exact-kernel controller costs O(N2)O(N^2) over a stream of NN queries, whereas the RFF controller costs O(D)O(D) per query with DD features. We ran the exact-kernel controller on all seven edge streams and all seven node streams using the same settings and seeds as RFF-512. Before rounding, coverage differs by less than 4×10−54 \times 10^{-5}. Set size changes by at most 1.2%, and the graph-local gap KK changes by at most 4.2%.

TaskDatasetCov. (RFF-512)Cov. (Exact)Size changeKK change
EdgeCora0.90000.9000−0.21%−2.2%
EdgeCiteSeer0.90000.9000−0.30%−2.2%
EdgePubMed0.90010.9001+0.01%+0.7%
EdgeComputers0.90030.9003−0.03%−0.6%
EdgeRoman-empire0.89990.8999−0.13%−2.0%
EdgeAmazon-ratings0.90000.9001+0.06%−1.1%
Edgeogbn-arxiv0.90010.9001+0.04%−0.4%
NodeCora0.90200.9020−0.12%−0.2%
NodeCiteSeer0.90000.9000−0.12%−1.8%
NodePubMed0.90040.9004−0.03%−3.9%
NodeComputers0.90010.9001−0.78%−0.2%
NodeRoman-empire0.90030.9003+1.18%+1.9%
NodeAmazon-ratings0.90000.9000−0.02%−1.1%
Nodeogbn-arxiv0.90000.9000−1.01%−4.2%

Percentage changes are computed as (Exact − RFF-512) / RFF-512. On the full ogbn-arxiv node stream, controller runtime drops from 85.9 s with the exact kernel to 0.93 s with RFF-512, a 92× speedup.

Number of anchors. We recomputed KK with 16, 32, 64 (default), 128, and 256 anchors. For 16–128 anchors, we used nested subsets of the calibration prefix. Because KK is a maximum over anchors, it can only increase or stay constant as these nested sets grow. We drew the 256 anchors from the post-prefix stream.

TaskDataset163264128256
EdgeCora0.00080.00080.00090.00100.0011
EdgeCiteSeer0.00120.00150.00170.00190.0021
EdgePubMed0.00030.00030.00030.00030.0003
EdgeComputers0.00270.00350.00400.00420.0044
EdgeRoman-empire0.00060.00060.00070.00090.0011
EdgeAmazon-ratings0.00050.00060.00070.00070.0007
Edgeogbn-arxiv0.00190.00200.00210.00220.0025
NodeCora0.00730.00810.00890.00990.0101
NodeCiteSeer0.00390.00450.00500.00530.0057
NodePubMed0.00470.00510.00550.00570.0061
NodeComputers0.01200.01340.01390.01470.0154
NodeRoman-empire0.01620.01760.01790.01820.0182
NodeAmazon-ratings0.00050.00050.00070.00070.0008
Nodeogbn-arxiv0.00210.00250.00280.00300.0031

Selection of anchors. With 64 anchors, we compared the default prefix sample, five independent redraws from the prefix, a uniform sample from the post-prefix stream, and k-means centers of the post-prefix representations.

TaskDatasetPrefix (default)Prefix (redrawn)Stream (uniform)Stream (k-means)
EdgeCora0.00090.00100.00100.0008
EdgeCiteSeer0.00170.00170.00160.0014
EdgePubMed0.00030.00030.00030.0003
EdgeComputers0.00400.00400.00400.0040
EdgeRoman-empire0.00070.00070.00080.0008
EdgeAmazon-ratings0.00070.00070.00050.0006
Edgeogbn-arxiv0.00210.00210.00200.0023
NodeCora0.00890.00920.00900.0083
NodeCiteSeer0.00500.00490.00510.0047
NodePubMed0.00550.00540.00550.0055
NodeComputers0.01390.01390.01430.0133
NodeRoman-empire0.01790.01790.01760.0168
NodeAmazon-ratings0.00070.00070.00070.0006
Nodeogbn-arxiv0.00280.00280.00270.0022

Across the tested anchor counts, KK varies by at most a factor of about two on each stream. Edge gaps are on the order of 10−410^{-4} to 10−310^{-3}, and node gaps are at most 0.0182. Across the four selection rules, the range of KK is about 0.001 or less on each stream. Across the five prefix redraws, the standard deviation of KK is 2–20% of its mean. For every tested anchor count and selection rule, the smaller gap of ACI and conformal PID is 10–63× GLocalCP's gap on edge streams and 2.1–11× GLocalCP's gap on node streams.

AuthorsOpenReview ↗

Response to Reviewer s6Sb (2/2): temporal shift and computational cost

Q2 / W2. Behavior under explicit temporal distribution shift

Real temporal shift (ogbn-arxiv). Nodes arrive in publication-year order. We measured coverage and the graph-local gap KK in publication-year windows and fixed-length sliding windows. Coverage deviation in window ww is ∣covw−0.9∣\lvert\mathrm{cov}_w - 0.9\rvert.

TaskWindowsMax. coverage deviationMean window KKMax. window KK
NodeBy year0.00040.00410.0100
Node5,000 queries, step 1,0000.00090.00480.0095
EdgeBy year0.00050.00360.0073
Edge1,000 queries, step 2000.00280.00690.0248

The maximum coverage deviation is below 0.003, and the window-level graph-local gap stays on the order of 10−210^{-2} or smaller.

Constructed label shift. We split the Computers and Roman-empire node streams into four segments. In each segment, about 80% of arriving nodes come from one group of classes, and the dominant group changes at each of the three switch points. We kept the predictor and all hyperparameters fixed.

DatasetArrival orderCoverageMean set sizeKK
ComputersRandom0.9001.4730.0139
ComputersLabel shift0.9001.6590.0138
Roman-empireRandom0.9005.3630.0179
Roman-empireLabel shift0.9005.1230.0161

Marginal coverage and the graph-local gap are essentially unchanged under label shift. Using sliding windows of 500 queries, the maximum absolute coverage deviation from 0.9 in the first 1,000 queries after a switch is 0.011 on Computers and 0.008 on Roman-empire, on average. Each segment contains about a quarter of the stream. Across segments, the graph-local gap averages 0.040 on Computers and 0.027 on Roman-empire.

Q3. Computational overhead of MC dropout and the set size–inference cost trade-off

For node classification, we report the mean set size of GLocalCP with MM stochastic passes and for a single deterministic pass with constant scale rn=1r_n = 1.

DatasetNo MC (rn=1r_n = 1)M=2M=2M=5M=5M=10M=10M=20M=20M=30M=30
Cora2.7082.7852.6272.5682.5282.527
Computers1.6691.6321.5181.4921.4751.473
Roman-empire6.3745.9765.6115.4635.3885.363
ogbn-arxiv14.18211.66310.97610.73810.60810.563

Coverage is 0.900–0.902 across all configurations. The default M=30M=30 reproduces Table 1. The “No MC” column here uses deterministic predictions. Table 2b uses MC-averaged predictions in its rn=1r_n = 1 column. Increasing MM from 20 to 30 reduces mean set size by less than 0.5% on all four datasets.

Runtime on the full ogbn-arxiv node stream.

ConfigurationInference (s)Controller (s)Mean set size
Single deterministic pass, rn=1r_n = 10.0190.92214.182
MC, M=5M=50.4150.96010.976
MC, M=10M=100.7300.90910.738
MC, M=30M=30 (default)2.1960.94410.563

Inference is batched over the graph and includes computation of the MI scale. Controller time covers set construction and online updates. Relative to a single deterministic pass, M=30M=30 increases inference time from 0.019 s to 2.196 s and reduces mean set size by 25.5%. The controller takes about 0.9 s across configurations. Reducing MM from 30 to 10 cuts inference time by a factor of three and increases mean set size by 1.7%.

MC dropout is optional. The guarantees hold for any predictable scale (Prop. B.3). The deterministic single-pass variant maintains coverage near 0.9 and produces larger sets than the default M=30M=30 on all four datasets.

Revisions. We will add these results to the appendix of the revised PDF and clarify in Sec. 5.1 that KK is computed over 64 audit anchors drawn from the calibration prefix.

AuthorsOpenReview ↗

Revised PDF uploaded

Dear Reviewer s6Sb,

Thank you again for your review. We have uploaded the revised PDF, with changes marked in blue. The points you raised are addressed in the following places: the exact-kernel versus RFF comparison in Appendix D.3, the anchor-based computation of KK in Sec. 5.1 and Appendix G.2, temporal and label shift in Appendix G.3, and the number of MC passes and its cost in Appendix F.5. We would appreciate it if you could let us know whether these address your concerns.

Reviewer_UvUMOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes GLocalCP, an online conformal method for inductive node and edge prediction. It extends ACI-style threshold updates with (i) a kernel-based local correction g_n(z) in the GNN embedding space, updated by kernel gradient descent on the coverage error, and (ii) an MC-dropout mutual-information scale on the nonconformity score. It proves pathwise O(N^{-1/2}) marginal and kernel-local calibration bounds and reports experiments on 7 datasets, where GLocalCP attains coverage 0.900 and the smallest kernel-local gap K everywhere.

Critical strengths

Clear motivation: marginal coverage says nothing about where errors occur on a graph, and the sequential inductive setting is realistic. Clean presentation, 50 seeds, and ablations that separate the two components across backbones, scores and candidate distributions.

Critical weaknesses

The evaluation metric is the method’s own objective. K is sup_z |Σ k(z,z_n)(err_n − α)| / Σ k(z,z_n), and g_N(z) = η Σ k(z,z_n)(err_n − α) is exactly the quantity GLocalCP drives toward zero, with the same RBF kernel and bandwidth (h = 0.5) used for evaluation. That GLocalCP has the smallest K on every dataset is close to a tautology. Local calibration should be assessed on criteria the method does not optimize: coverage conditional on degree, class, homophily, community, arrival time, or at least a different kernel/bandwidth. The baselines are not online methods. NAPS-U, DAPS and SNAPS are calibrated once on a 200-query prefix and receive no feedback, so their drift to 0.73–0.85 coverage is expected and uninformative. The natural baselines are missing from Table 1: plain ACI (which is the “Global MI” ablation), DtACI / conformal PID, Mondrian or class-conditional online CP, and the kernel/feature-based conditional methods of Gibbs, Cherian & Candès (2023), Bastani et al. (2022), and Lai & Raskutti (2026), which the paper cites only in the appendix and does not compare against. The theory is standard and the local bound is vacuous. Theorem 3.1 is the usual potential argument for online gradient descent; it even gives a weaker rate (N^{-1/2}) than ACI’s O(1/N) and the paper does not explain why. Theorem 4.1 scales with 1/k_min, where for the RBF kernel k_min = e^{-2/h²}; at the paper’s h = 0.5 this is e^{-8} ≈ 3·10⁻⁴, so the bound exceeds 1 for every N used. The bound also applies only to the exact kernel, while experiments use RFF, as the authors acknowledge. The MI scale has no theoretical role (Prop. B.3).

Questions for authors

How does GLocalCP perform on local-coverage criteria it does not optimize (degree buckets, class-conditional, community-wise), and with an evaluation bandwidth different from the controller’s? Please add ACI, DtACI/PID and an online localized CP baseline to Table 1. What is the numerical value of the Theorem 4.1 bound at h = 0.5 for your N, and how does the choice of h trade locality against the bound? Why is the marginal rate N^{-1/2} rather than ACI’s 1/N?

5 comments
AuthorsOpenReview ↗

Response to Reviewer UvUM (1/3): K and criteria GLocalCP does not optimize

Response to Reviewer UvUM (1/3): K and criteria GLocalCP does not optimize

We thank the reviewer for the careful review. All results are averaged over 50 seeds on 7 edge and 7 node streams.

Q1 / W1.

What KK measures. For an anchor zz in the inductive representation space, each query is weighted by its similarity k(z,zn)k(z,z_n), and EN(z)E_N(z) is the weighted miscoverage rate minus α\alpha; KK is the largest such error over the anchors. It measures how far coverage is from the target among queries with similar graph context, which marginal coverage cannot detect: on Cora edges ACI and GLocalCP both have marginal coverage 0.900, but their KK is 0.0420 and 0.0009. The neighborhoods are soft and overlapping, induced by zn(v)=gθ(xv,Nv(Gn))z_n(v)=g_\theta(x_v,\mathcal N_v(\mathcal G_n)) (Eq. (3) for edges), so no grouping is specified in advance; a small EN(z)E_N(z) means coverage stays near 1−α1-\alpha when the stream shifts toward the neighborhood of zz (the kernel instance of Gibbs, Cherian & Candès, 2023), as happens in evolving graphs where new nodes concentrate in particular regions.

Groupings not used by the method: degree, community and class. We agree that KK should be complemented by criteria the method does not optimize. These groupings are not given to GLocalCP and are not targeted by KK. On edge degree GLocalCP has the smallest gap on 7/7 datasets; on the node groupings the result varies with the grouping and the dataset, and we report the exceptions; coverage by arrival-time window on ogbn-arxiv is in our response to Reviewer s6Sb (part 2/2). Tables give max⁡g∣covg−0.9∣\max_g\lvert\mathrm{cov}_g-0.9\rvert.

Edge degree (quintiles). GLocalCP is the smallest of all ten methods on all seven datasets: 2.3–5.5× smaller than the next best on five (CiteSeer 0.0094 vs. 0.0513; Cora 0.0109 vs. 0.0415; Roman-empire 0.0101 vs. 0.0251) and 1.3× on Amazon-ratings and ogbn-arxiv.

DatasetGLocalCPACIPIDOLCPMVPGCCCLP-CQRCLP-SCQRRR-CQRRR-Mondrian
Cora.0109.0705.0415.1157.1224.2382.1012.1005.0575.0638
CiteSeer.0094.0699.0513.1368.1203.1880.0894.0886.0742.0706
PubMed.0182.0657.0416.2208.2129.2531.0968.0988.1019.0969
Computers.0166.0473.0380.0835.0608.0671.0685.0652.0957.0816
Roman-empire.0101.0451.0251.0655.0546.0579.1097.1141.0588.0560
Amazon-ratings.0105.0277.0140.2238.1859.2443.0680.0664.0592.0560
ogbn-arxiv.0467.0912.0620.1715.1091.1147.0983.1009.0855.0728

Community (Louvain, nodes). GLocalCP leads by a wide margin on Computers (0.1998 vs. 0.3490) and leads on Cora (0.1694 vs. 0.1935); it is within 0.005 of the best on CiteSeer, PubMed, Roman-empire and ogbn-arxiv, and close to ACI and PID on Amazon-ratings.

DatasetGLocalCPACIPIDOLCPMVPGCCDAPSSNAPS
Cora.1694.2217.1935.2978.3261.2845.4868.4895
CiteSeer.1100.1191.1110.1468.1630.1425.3878.3268
PubMed.1369.1544.1532.1531.1723.1381.3094.2717
Computers.1998.3656.3490.4002.4092.4010.5234.5623
Roman-empire.0970.1123.1020.1133.0920.0993.2709.2633
Amazon-ratings.2735.2648.2388.3134.3221.3021.4162.4268
ogbn-arxiv.3225.6187.3202.4165.3868.3636.6115.6152

Node degree. GLocalCP leads on Roman-empire (0.0152 vs. 0.0199) and CiteSeer (0.0205 vs. 0.0249), is within 0.003 of the best on Cora, PubMed and Amazon-ratings, is second-best on ogbn-arxiv, and is behind DAPS, SNAPS and OLCP on Computers (0.0652 vs. 0.0411).

DatasetGLocalCPACIPIDOLCPMVPGCCDAPSSNAPS
Cora.0214.0218.0231.0535.0342.0470.1793.1607
CiteSeer.0205.0249.0290.0511.0347.0342.3170.2569
PubMed.0092.0094.0089.0323.0182.0132.1421.0946
Computers.0652.0734.0728.0615.0686.0700.0501.0411
Roman-empire.0152.0412.0454.0651.0199.0441.2911.3250
Amazon-ratings.0243.0253.0214.0589.0536.0457.0905.0940
ogbn-arxiv.0403.0669.0602.0851.0287.0558.0888.0935

Class. Although class-conditional coverage is outside the scope of kernel-local calibration (Sec. 4), GLocalCP leads by a wide margin on Computers (0.3244 vs. 0.4601), leads on Cora, PubMed and Amazon-ratings, and is within 0.006 of the best on CiteSeer and ogbn-arxiv; on Roman-empire the localized baselines are better (0.2998 vs. 0.2054 for MVP).

DatasetGLocalCPACIPIDOLCPMVPGCCDAPSSNAPS
Cora.1931.2584.2109.4064.4583.3904.4904.5036
CiteSeer.3089.3954.3029.5468.6717.5969.5375.5661
PubMed.0238.0259.0266.0295.0321.0293.1242.0900
Computers.3244.4969.4752.4601.4961.4644.7039.7357
Roman-empire.2998.5012.3246.2223.2054.2395.7378.7588
Amazon-ratings.5981.8023.6476.6477.7296.6667.8343.8366
ogbn-arxiv.4029.8586.4087.5883.5253.5810.8254.8254
AuthorsOpenReview ↗

Response to Reviewer UvUM (2/3): Q1 / W1 continued; Q3 / W3, Theorem 4.1

Q1 / W1 (continued).

Other evaluation bandwidths. Keeping the controller fixed (RBF, h=0.5h=0.5) and changing only the audit bandwidth tests whether the result depends on the evaluation scale (heval=0.5h_{\rm eval}=0.5 is in part 3/3). Cells give KK at heval=0.25/1/2h_{\rm eval}=0.25/1/2; "Graph" is the best of CLP-CQR, CLP-SCQR, RR-CQR, RR-Mondrian (edges) or DAPS, SNAPS (nodes). KK itself changes with the bandwidth for every method, but the comparison does not: on edges GLocalCP has the lowest KK in 21/21 settings, 4.8–47× below the best baseline. On nodes it has the lowest KK in most settings, by up to 17×; the exceptions are Computers and Roman-empire at heval=0.25h_{\rm eval}=0.25 (some localized baselines) and Cora at heval=2h_{\rm eval}=2 (ACI, PID).

Edge (1:10)GLocalCPACIPIDOLCPMVPGCCGraph
Cora.0065/.0003/.0001.1315/.0113/.0029.0923/.0074/.0019.1415/.0127/.0034.0986/.0120/.0063.1568/.0345/.0288.0716/.0311/.0279
CiteSeer.0104/.0005/.0002.1762/.0141/.0036.1423/.0108/.0027.1584/.0131/.0035.1346/.0104/.0051.1701/.0238/.0173.0948/.0381/.0335
PubMed.0018/.0001/.0001.0795/.0059/.0015.0588/.0047/.0012.1323/.0152/.0040.0939/.0113/.0068.1142/.0245/.0193.1534/.0458/.0397
Computers.0215/.0012/.0005.1035/.0108/.0027.1030/.0100/.0024.1436/.0250/.0073.1460/.0270/.0099.1422/.0316/.0149.1042/.0314/.0260
Roman-empire.0057/.0002/.0001.1183/.0085/.0022.0669/.0042/.0011.0384/.0028/.0008.0349/.0032/.0018.0430/.0103/.0081.0778/.0254/.0232
Amazon-ratings.0067/.0002/.0001.0721/.0046/.0012.0700/.0036/.0009.1228/.0141/.0039.0818/.0113/.0055.1082/.0163/.0107.1115/.0405/.0376
ogbn-arxiv.0118/.0006/.0003.0640/.0061/.0015.1419/.0058/.0015.3274/.0241/.0057.2867/.0190/.0066.3011/.0228/.0108.1865/.0520/.0491
NodeGLocalCPACIPIDOLCPMVPGCCGraph
Cora.0507/.0029/.0022.0692/.0048/.0013.0673/.0053/.0020.0867/.0078/.0022.1048/.0180/.0114.0881/.0166/.0122.2853/.1303/.1204
CiteSeer.0344/.0014/.0007.0515/.0029/.0009.0472/.0035/.0016.0486/.0037/.0013.0597/.0160/.0128.0575/.0112/.0087.2254/.1408/.1348
PubMed.0349/.0007/.0004.0784/.0062/.0016.0779/.0064/.0017.0686/.0085/.0021.0873/.0151/.0066.0712/.0122/.0080.1698/.0581/.0504
Computers.0962/.0019/.0006.2103/.0131/.0031.2116/.0131/.0032.0936/.0113/.0027.1130/.0202/.0108.0894/.0146/.0079.3213/.0404/.0279
Roman-empire.0946/.0027/.0008.1129/.0124/.0032.1036/.0124/.0032.0787/.0068/.0016.0683/.0043/.0024.0714/.0107/.0076.3192/.1627/.1430
Amazon-ratings.0123/.0002/.0001.0336/.0016/.0004.0326/.0017/.0004.0424/.0053/.0013.0424/.0095/.0068.0401/.0092/.0056.1364/.0719/.0698
ogbn-arxiv.0375/.0002/.0001.0680/.0033/.0008.0720/.0038/.0009.0856/.0101/.0024.0783/.0069/.0028.0799/.0138/.0096.1211/.0397/.0364

Other kernels. Evaluating with a Matérn kernel instead of RBF, KK on Cora edges is 0.0009 for both Matérn-3/2 and Matérn-5/2 (0.0009 under RBF), and on ogbn-arxiv nodes it is 0.0025 for Matérn-3/2 and 0.0027 for Matérn-5/2 (0.0028 under RBF). Using either Matérn kernel in the controller gives the same coverage, set sizes within about 1%, and gaps of the same magnitude.

Q3 / W3. Theorem 4.1: the bound, the role of hh, RFF and MI. Theorem 4.1 is a worst-case convergence guarantee over all sequences and anchors, as is standard in adversarial online CP (Bastani et al., 2022; Angelopoulos et al., 2024); its constant assumes every query lies at the maximal distance from the anchor, and guarantees for kernel-based conditional CP likewise weaken where the local kernel mass is small (Liu et al., 2025). On ogbn-arxiv nodes (N=148,821N=148{,}821) it evaluates to 74.0, 0.18 and 0.04 at h=0.5h=0.5, 11 and 22, while the realized gap at h=0.5h=0.5 is 0.0028. A smaller hh localizes more finely but has a larger worst-case constant; as h→∞h \to \infty the weights become uniform and the bound recovers Theorem 3.1.

RFF and MI. Theorem 4.1 is stated for the exact kernel; RFF approximates it to reduce cost. The marginal analysis carries over: with state (qn,wn)(q_n,\mathbf{w}_n) and Φn=(1,ϕ(zn))\Phi_n=(1,\phi(z_n)), ∥ϕ(z)∥22=1\lVert\phi(z)\rVert_2^2=1 gives ∥Φn∥22=2\lVert\Phi_n\rVert_2^2=2, so Lemma B.2 and Theorem 3.1 apply to the RFF controller. Empirically, the exact-kernel and RFF-512 controllers are essentially indistinguishable: coverage differs by less than 4×10−54 \times 10^{-5}, set size by at most 1.2% and KK by at most 4.2% (per-stream table in our response to Reviewer s6Sb, part 1/2), while RFF is about 92× faster on ogbn-arxiv nodes (0.93 s vs. 85.9 s). For MI, the guarantees hold for any predictable rn∈[γr,1]r_n \in [\gamma_r,1] (Prop. B.3); its role is efficiency: at unchanged coverage it reduces set size by 1.7–6.4% on edges and 2.8–23.9% on nodes (Table 2b).

AuthorsOpenReview ↗

Response to Reviewer UvUM (3/3): Q4 / W3, the rate; Q2 / W2, online baselines

Q4 / W3. The N−1/2N^{-1/2} rate and ACI's 1/N1/N. The potential technique is standard; the difference is structural. ACI's 1/N1/N rate relies on its scalar threshold being confined to a bounded interval, since the threshold alone decides coverage. In GLocalCP coverage is decided by the sum qn+gn(zn)q_n+g_n(z_n), so this self-correction applies to the sum rather than to qnq_n; we therefore control the joint potential ∥(q,g)∥2≤NC\lVert(q,g)\rVert^2\le NC, which gives N−1/2N^{-1/2}. We make no optimality claim; realized coverage is 0.900–0.902 on every stream.

Q2 / W2. Online baselines. Existing CP methods for inductive and temporal graphs mainly restore or relax exchangeability through the calibration construction or the score design (e.g., Zargarbashi & Bojchevski, 2024; Wang et al., 2025); calibration driven by sequential coverage feedback has, to our knowledge, received much less attention on inductive graph streams, where existing online methods face two difficulties. (i) A single global threshold is insufficient: ACI-type methods avoid exchangeability, but uncertainty varies with graph context, and a global threshold offsets under-coverage in some neighborhoods with over-coverage in others. (ii) Localization needs a space: OLCP (Lai & Raskutti, 2026), MVP (Bastani et al., 2022) and GCC (Gibbs, Cherian & Candès, 2023) are defined on input covariates, but raw features ignore the neighborhood, do not change as the graph grows, and are undefined for edge queries. Our formulation supplies this space through zn(v)=gθ(xv,Nv(Gn))z_n(v)=g_\theta(x_v,\mathcal N_v(\mathcal G_n)) and the pair representation in Eq. (3).

GLocalCP keeps the ACI-style global update and adds kernel feedback on zz. ACI and conformal PID use only the scores; OLCP, MVP and GCC are given the same zz for a fair comparison. Cells report Cov/Size/KK.

Edge (1:10)ACIPIDOLCPMVPGCCGLocalCP
Cora.900/1.70/.0420.900/1.74/.0278.900/1.78/.0451.902/1.76/.0318.874/1.76/.0577.900/1.56/.0009
CiteSeer.900/1.72/.0557.900/1.76/.0444.900/1.66/.0512.902/1.65/.0337.888/1.67/.0549.900/1.58/.0017
PubMed.900/1.46/.0237.900/1.62/.0188.900/1.86/.0529.896/1.79/.0308.883/1.79/.0447.900/1.45/.0003
Computers.900/1.45/.0439.900/1.46/.0418.901/1.35/.0771.902/1.44/.0791.907/1.51/.0786.900/1.37/.0040
Roman-empire.900/1.55/.0319.900/1.67/.0165.900/1.34/.0107.899/1.39/.0099.907/1.44/.0183.900/1.54/.0007
Amazon-ratings.900/1.47/.0188.900/1.57/.0141.900/1.87/.0462.900/1.85/.0296.894/1.85/.0386.900/1.44/.0007
ogbn-arxiv.900/1.30/.0250.900/1.40/.0251.900/1.58/.1124.901/1.65/.0852.905/1.71/.0875.900/1.33/.0021
NodeACIPIDOLCPMVPGCCGLocalCP
Cora.900/2.55/.0188.900/3.58/.0190.900/3.25/.0286.891/3.33/.0421.904/3.28/.0343.902/2.53/.0089
CiteSeer.900/3.00/.0114.899/3.70/.0112.900/3.54/.0137.890/3.52/.0276.903/3.62/.0218.900/2.97/.0050
PubMed.900/1.19/.0204.900/1.17/.0206.900/1.39/.0282.896/1.31/.0415.906/1.40/.0297.900/1.16/.0055
Computers.900/1.42/.0584.900/1.83/.0580.900/3.79/.0435.892/3.99/.0543.905/3.88/.0430.900/1.47/.0139
Roman-empire.900/3.86/.0469.900/9.54/.0490.900/11.31/.0324.902/12.58/.0189.907/10.88/.0290.900/5.36/.0179
Amazon-ratings.900/3.38/.0063.900/3.56/.0062.900/3.49/.0184.894/3.41/.0202.904/3.53/.0199.900/3.35/.0007
ogbn-arxiv.900/6.77/.0142.900/21.79/.0162.900/10.01/.0388.899/16.42/.0263.908/10.78/.0366.900/10.56/.0028
  • Marginal coverage is on par with ACI and PID (0.899–0.902), which follows from the shared global update.
  • Local gap. GLocalCP has the smallest KK on all 14 streams: 10–63× smaller than the best of the five baselines on edges and 2.1–9.5× on six node datasets; on Roman-empire nodes the margin over MVP is small (0.0179 vs. 0.0189).
  • A good representation alone is not enough; the gain comes from the kernel feedback state. Given the same zz, OLCP, MVP and GCC do not improve on the global methods: their KK is at or above the better of ACI and PID on five of seven edge datasets (ogbn-arxiv 0.085–0.112 vs. 0.025; Computers 0.077–0.079 vs. 0.042). The reduction comes from propagating each coverage error to similar queries through gng_n.
  • Set size. On edges GLocalCP has the smallest sets on four datasets and is within 0.03 of the smallest on Computers and ogbn-arxiv; the localized baselines are smaller on Roman-empire. On nodes its sets are smaller than those of PID, OLCP, MVP and GCC on six datasets and comparable to ACI's on four.

Mondrian and class-conditional CP target a partition fixed in advance, a different objective; online group-conditional calibration is represented by MVP.

Revisions. We will add the five online baselines to Table 1 and the group-gap, bandwidth, kernel and exact-kernel results to the appendix in the revised PDF.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the discussion and revisions for the Area Chair

Dear Area Chair,

Thank you for handling our submission. We also thank all reviewers for their careful reading and constructive feedback. A revised PDF has been uploaded, with all changes marked in blue and the main text within 10 pages. Below we summarize the outcome of the discussion with each reviewer.

Reviewer UvUM

Reviewer UvUM indicated satisfaction with the rebuttal and increased the score from 2 to 3. The concerns were resolved as follows.

  • Missing baselines with sequential feedback. Five online baselines (ACI, conformal PID, OLCP, MVP, GCC) are added to Table 1. ACI, PID, and OLCP reach coverage 0.900 on nearly every stream, yet GLocalCP has the smallest KK on all 14 streams, 10–63× smaller than the best of them on edges.
  • Evaluation beyond KK. Appendix G.1 reports coverage gaps over edge-degree, community, node-degree, and class groups, and KK under other bandwidths and Matérn kernels. On edges, GLocalCP has the smallest degree gap on all seven datasets and the lowest KK in all settings at other bandwidths; on nodes, it is the best or close to the best in most cases, and the exceptions are reported.
  • Theorem 4.1. The role of the bandwidth in the bound and the N−1/2N^{-1/2} rate are clarified in our response, and the exact-kernel and RFF controllers are compared in Appendix D.3.

Reviewer R1CE

Reviewer R1CE confirmed that all concerns were addressed and increased the score from 2 to 3. The concerns were resolved as follows.

  • Task setup. Sec. 2 now states that the prediction task is fixed per stream, and Algorithm 1 takes the task as an input.
  • Comparison with NodeEx CP. Added to Table 1 under the same protocol; GLocalCP has a smaller local gap KK on all seven node datasets.
  • Relation to GraphLCP. Discussed in the related work.
  • Global MI ablation and the estimation of KK. The appendix reports the marginal coverage and set size of Global MI, and Appendix G.2 evaluates KK with up to 1024 anchors.

Reviewer s6Sb

Reviewer s6Sb gave a rating of 3. All points raised are answered in our response and addressed in the revision as follows.

  • RFF approximation. Appendix D.3 compares the exact-kernel and RFF controllers: set size and KK differ by at most 1.2% and 4.2%, while RFF is about 92× faster.
  • Audit anchors. Appendix G.2 varies the number of anchors from 16 to 1024 and the selection rule; from 64 to 1024 anchors, KK changes by at most 0.0022 on nodes and 0.0007 on edges.
  • Temporal shift. Appendix G.3 reports windowed results on ogbn-arxiv, where coverage stays within 0.003 of the target, and a constructed label-shift stream.
  • Cost of MC dropout. Appendix F.5 reports set size and inference time for different numbers of MC passes.

We are grateful to Reviewers UvUM and R1CE for acknowledging our responses and raising their scores. We thank the Area Chair and all reviewers again for their time and effort.

Best regards, The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.