- 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 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" is computed as the maximum of a finite set () 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 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 and 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
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 () and the same kernel; the default 64 anchors come from the calibration prefix. The table reports for GLocalCP, and for ACI and conformal PID at 1024 anchors.
| Task | Dataset | GLocalCP, 64 (default) | GLocalCP, 256 | GLocalCP, 512 | GLocalCP, 1024 | ACI, 1024 | PID, 1024 |
|---|---|---|---|---|---|---|---|
| Edge | Cora | 0.0009 | 0.0011 | 0.0012 | 0.0012 | 0.0456 | 0.0312 |
| Edge | CiteSeer | 0.0017 | 0.0021 | 0.0022 | 0.0023 | 0.0645 | 0.0520 |
| Edge | PubMed | 0.0003 | 0.0003 | 0.0003 | 0.0003 | 0.0253 | 0.0199 |
| Edge | Computers | 0.0040 | 0.0044 | 0.0045 | 0.0047 | 0.0470 | 0.0449 |
| Edge | Roman-empire | 0.0007 | 0.0011 | 0.0013 | 0.0014 | 0.0420 | 0.0235 |
| Edge | Amazon-ratings | 0.0007 | 0.0007 | 0.0007 | 0.0008 | 0.0207 | 0.0157 |
| Edge | ogbn-arxiv | 0.0021 | 0.0025 | 0.0025 | 0.0026 | 0.0264 | 0.0294 |
| Node | Cora | 0.0089 | 0.0101 | 0.0107 | 0.0111 | 0.0222 | 0.0221 |
| Node | CiteSeer | 0.0050 | 0.0057 | 0.0060 | 0.0061 | 0.0134 | 0.0126 |
| Node | PubMed | 0.0055 | 0.0061 | 0.0063 | 0.0065 | 0.0223 | 0.0225 |
| Node | Computers | 0.0139 | 0.0154 | 0.0158 | 0.0160 | 0.0636 | 0.0635 |
| Node | Roman-empire | 0.0179 | 0.0182 | 0.0183 | 0.0183 | 0.0476 | 0.0495 |
| Node | Amazon-ratings | 0.0007 | 0.0008 | 0.0010 | 0.0011 | 0.0081 | 0.0081 |
| Node | ogbn-arxiv | 0.0028 | 0.0031 | 0.0033 | 0.0034 | 0.0180 | 0.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 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 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 is the maximum of 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 . 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 : we want a method that is calibrated both marginally and locally, with and 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 , 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.
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.
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), 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)." 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.
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 K 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 K 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.