PaperlayerView exact revision on arXiv

Source-linked AI summary

Distribution Free Prediction Sets for Node Classification

Jase Clarkson

arXiv:2211.14555v3stat.MLcs.LG

TL;DR

Graph dependence makes rigorous uncertainty quantification for GNN predictions difficult, and naive conformal prediction lacks guarantees when graph data are non-exchangeable. The paper adapts conformal prediction for inductive node classification by weighting scores to reflect network structure; experiments report tighter, better-calibrated sets than the naive approach. Its recommended setting is large homophilous networks with dense one- or two-hop neighborhoods.

  • Problem

    Graph-induced dependence makes GNN predictive uncertainty difficult to quantify, and naive conformal prediction’s guarantees do not hold for generally non-exchangeable graph data.

    Source: §1 · p. 1

  • Method

    NAPS adapts conformal prediction to inductive node classification by weighting conformal scores to reflect graph structure and localizing calibration.

    Source: §1 · p. 1, §3.1 · p. 3, §4 · p. 3

  • Results

    Across the evaluated models and datasets, NAPS produces well-calibrated, tight prediction sets while naive APS tends to overcover and produce wider sets.

    Source: §6.3 · p. 6

  • Takeaways & Limitations

    NAPS is presented as a quick-to-deploy approach with theoretical coverage guarantees and more efficient prediction sets with better conditional coverage than naive conformal prediction.

    Source: §9 · p. 8

    The presented approach is recommended only for large homophilous networks with dense one- or two-hop neighborhoods, and its training setup excludes the transductive setting.

    Source: §4 · pp. 3–4

Abstract

from arXiv · show

Graph Neural Networks (GNNs) are able to achieve high classification accuracy on many important real world datasets, but provide no rigorous notion of predictive uncertainty. Quantifying the confidence of GNN models is difficult due to the dependence between datapoints induced by the graph structure. We leverage recent advances in conformal prediction to construct prediction sets for node classification in inductive learning scenarios. We do this by taking an existing approach for conformal classification that relies on \textit{exchangeable} data and modifying it by appropriately weighting the conformal scores to reflect the network structure. We show through experiments on standard benchmark datasets using popular GNN models that our approach provides tighter and better calibrated prediction sets than a naive application of conformal prediction.

1. Introduction

Although GNNs are popular and successful, their predictive uncertainty remains difficult to quantify because graph structure makes datapoints dependent. The paper adapts conformal prediction to node classification by weighting scores to reflect network structure, reporting tighter and better-calibrated sets than naive conformal prediction.

1. Introduction

  • GNNs have achieved popularity and success, but rigorous uncertainty quantification for their predictions has seen little progress.The paper describes uncertainty quantification as vital for robust real-world deployments.Source: §1 · p. 1
  • Graph dependence generally violates exchangeability, so naive conformal prediction’s guarantees do not hold for networks.The paper draws on non-exchangeable conformal prediction and localizes calibration using the idea that calibration should be similar within a homophilous graph neighborhood.Source: §1 · p. 1
  • Across several state-of-the-art models and popular node-classification datasets, the method yields tighter, better-calibrated prediction sets than naive conformal prediction.The paper adapts conformal classification by weighting scores to reflect network structure.Source: §1 · p. 1

2. Related Work

Prior uncertainty methods include Bayesian approaches and conformal prediction, while graph-specific Bayesian methods modify the model or training procedure. For non-exchangeable data, the paper distinguishes its graph-adjacency approach from time-series methods that use online learning or game-theoretic techniques.

2. Related Work

  • Bayesian methods represent uncertainty through a distribution over network weights, but can become computationally intractable for large models and datasets.Deep Ensembles and Variational Inference approximate Bayesian learning, with practical drawbacks including the need for Deep Ensembles to explore distinct parameter-space regions.Source: §2 · pp. 1–2
  • Proposed Bayesian GNN variants require model-architecture or training-procedure modifications, whereas this paper’s methods are deployed after training with trivial overhead relative to model fitting.The graph Bayesian variants cited are Hasanzadeh et al. (2020), Chandra et al. (2021), and Zhang et al. (2019).Source: §2 · p. 2
  • Conformal prediction also covers regression intervals and general risk control; for non-exchangeable time series, prior methods use online or game-theoretic techniques, unlike this paper’s assumption that graph adjacency indicates dependency.The paper focuses on conformal classification as introduced by Romano et al. (2020).Source: §2 · p. 2

3. Conformal Prediction

Split conformal prediction wraps a fitted model with held-out calibration data to construct finite-sample-valid prediction sets. The paper reviews exchangeable calibration with APS scores, then describes weighted quantiles and coverage-gap bounds for non-exchangeable data.

3. Conformal Prediction

  • Split conformal prediction uses exchangeable held-out data to calibrate prediction sets around a fitted model, and its guarantees do not require the predictive model to be well specified.The paper uses conformal prediction as a framework for finite-sample-valid prediction sets from arbitrary black-box models.Source: §3 · p. 2

3.1. The Exchangeable Case

  • In the exchangeable case, calibration scores determine an empirical quantile threshold, while APS measures the deviation from the oracle procedure needed to attain target coverage.APS uses randomized tie-breaking; the example describes adjusting the threshold when calibration coverage differs from the target.Source: §3.1 · pp. 2–3

3.2. Beyond Exchangeability

  • Beyond exchangeability, deterministic weights define weighted score quantiles, and the coverage-gap bound favors larger weights on datapoints drawn from a distribution similar to the test point.The paper describes coverage gap as loss of coverage relative to the exchangeable setting and bounds it using total variation distance.Source: §3.2 · p. 3

4. Conformal Prediction for Node Classification

NAPS adapts non-exchangeable conformal prediction to node classification by using graph adjacency to localize calibration around each test node. It also allows distance-weighted neighborhoods, but is intended for inductive settings and its neighborhood depth trades calibration sample size against topological similarity.

4. Conformal Prediction for Node Classification

  • NAPS combines non-exchangeable conformal prediction with graph adjacency to construct node-classification prediction sets.Its underlying observation is that adjacency conveys dependencies between datapoints, and neighborhood information is used for prediction.Source: §4 · p. 3
  • The unweighted NAPS variant calibrates with APS scores from nodes in the test node’s K-hop neighborhood.The coverage-gap bound is small when those neighbors are distributed similarly, as under homophily.Source: §4 · p. 4
  • Two distance-weighted variants give closer neighbors greater weight: NAPS-H uses hyperbolic decay and NAPS-G uses geometric decay.Their weights depend on the hop distance from the test node.Source: §4 · p. 4
  • NAPS applies in inductive settings, but not transductively, where test-node features would make the fitted model’s conformal scores non-exchangeable.Inductive settings include multiple new test graphs or new nodes added to an existing network.Source: §4 · p. 4
  • Increasing neighborhood depth K adds calibration nodes but may include nodes that are less topologically similar.The authors recommend applying NAPS only to large homophilous networks with dense one- or two-hop neighborhoods.Source: §4 · p. 4

5. A Case Study: The Stochastic Block Model

The case study uses a two-community stochastic block model to examine when neighborhood calibration can outperform calibration over all nodes. It gives an expected coverage-gap comparison for NAPS and APS, plus a mean-field approximation expressed in terms of data-generating parameters.

5. A Case Study: The Stochastic Block Model

  • The stochastic block model has two communities with different data distributions, and community membership is unobserved.Within- and between-community connection probabilities are denoted pin and pout.Source: §5 · p. 4
  • When pin is much larger than pout and there are enough neighbors, linked nodes are more likely to share a community, making neighbor calibration preferable to using all nodes.If community membership were known, calibration within a community would use exchangeable nodes drawn from the same distribution.Source: §5 · pp. 4–5
  • Lemma 5.1 gives a condition under which the expected coverage gap for unweighted, one-hop NAPS is lower than for APS.The passage also describes a mean-field approximation of this comparison in terms of data-generating parameters, but does not provide the condition’s readable expression.Source: §5 · p. 5

6. Experiments

Experiments on three node-classification datasets compare NAPS with naive APS across popular GNN models. NAPS produces well-calibrated, tighter prediction sets across the tested datasets and models, including Flickr with relatively weak homophily.

6. Experiments

  • The inductive evaluation holds test nodes out of model fitting and uses them to assess empirical coverage of constructed prediction sets.The setup is designed to evaluate how accounting for graph structure affects conformal prediction.Source: §6 · p. 5, §6.1 · p. 5

6.1. Evaluating Conformal Prediction

  • Observed coverage varies with calibration-node choice and finite calibration-set size, so experiments repeat calibration/evaluation splits using at least 1,000 validation points.The authors repeat each experiment 100 times to reduce the chance that deviations from true coverage dominate evaluation.Source: §6.1 · p. 5

6.2. Experimental Setup

  • Each experiment compares NAPS with APS calibrated on nodes outside the evaluation set, reporting empirical coverage and prediction-set size measures.Experiments sample 1,000 test nodes per repetition and repeat 100 times; NAPS is applied to large connected test components.Source: §6.2 · p. 5, Table 2 · p. 6

6.3. Datasets and Models

  • The study uses Reddit2, Flickr, and Amazon Computers with GraphSAGE mean/max and ShaDow with GraphSAGE or GCN layers; Reddit2 and Amazon Computers are strongly homophilous, unlike Flickr.Homophily is measured on induced test-node subgraphs against expected homophily under random label assignment.Source: §6.3 · p. 6
  • Across all models and three datasets, NAPS produces well-calibrated, tight prediction sets, while naive APS tends to overcover and produce wider sets.NAPS also outperforms APS on Flickr, where strong homophily is not required, and the result persists across GNN architectures.Source: §6.3 · p. 6, Table 2 · p. 6

7. Conditional Coverage and Network Topology

The section evaluates conditional coverage with a size-stratified metric and a graph-partition metric. Across datasets and models, all NAPS variants outperform APS on both measures.

7. Conditional Coverage and Network Topology

  • Exact conditional coverage is impossible for conformal prediction, but approximate conditional coverage remains desirable.The section evaluates NAPS using two conditional-coverage metrics.Source: §7 · p. 6
  • SSCV measures worst-case coverage violation across strata of prediction-set sizes, which serve as a proxy for sample difficulty.The metric is introduced for classification problems and stratifies possible set sizes.Source: §7 · p. 7
  • PCCV measures whether coverage varies across graph partitions, addressing cases where aggregate coverage masks sharply different community-level predictions.The paper motivates this metric with a 90/10 community example in which aggregate 90% coverage could still be unhelpful.Source: §7 · p. 7
  • For PCCV, calibration and test nodes are split in half, and test nodes are recursively grouped into 2-hop neighborhoods of at least 30 nodes.The procedure is repeated 100 times, with the median reported; SSCV uses the Section 6.2 setup.Source: §7 · p. 7
  • All NAPS variants outperform APS across datasets and models on conditional-coverage metrics; linear weights tend to perform best on Reddit2 and geometric weights on Amazon.Unweighted NAPS performs well across all datasets.Source: §7 · p. 7

8. Ablation Study

The ablation varies neighborhood depth K on Reddit2 to examine its trade-off between sample size and datapoint similarity. Weighted NAPS variants maintain coverage and set size better as neighborhoods grow.

8. Ablation Study

  • Neighborhood depth K trades off sample size against similarity between datapoints; the Reddit2 ablation tests K = 1 through 4.The experiment uses the Section 6.2 setup and GraphSAGE-Mean results are shown in Figure 2.Source: §8 · pp. 7–8
  • As K increases, weighted NAPS variants maintain similar coverage and prediction-set size, while unweighted NAPS tends toward APS.At K = 1, all NAPS variants coincide and slightly overcover, likely because of low sample size.Source: §8 · p. 8, Figure 2 · p. 8

9. Conclusion and Future Work

NAPS constructs prediction sets on graph-structured data and, in experiments, produces more efficient sets with better conditional coverage than naive conformal prediction. The conclusion also identifies limitations and possible extensions, including neighborhood-size selection and low-density networks.

9. Conclusion and Future Work

  • NAPS produces more efficient prediction sets with better conditional coverage properties than a naive application of conformal prediction.The authors also report theoretical coverage guarantees and describe NAPS as quick to train and deploy.Source: §9 · p. 8
  • Neighborhood size K is treated as a hyperparameter, and choosing it involves balancing local calibration nodes against a large enough sample for quantile estimation.The authors identify its interplay with homophily and network diameter as a topic for further study.Source: §9 · p. 8
  • The authors propose extending NAPS to heterophilic networks using alternating neighborhoods and to weighted, directed, or node-regression settings.For node regression, they suggest using a different conformal score function such as CQR.Source: §9 · p. 8
  • NAPS may produce wide prediction sets on low-density networks because conformal calibration has a small sample size.For small connected components, the authors suggest pooling calibration across similar neighborhoods or components to improve quantile estimation.Source: §9 · p. 8

10. Ethical Concerns

The authors do not expect negative societal impact, but caution that statistical predictions require careful interpretation, especially in high-stakes fields such as healthcare.

10. Ethical Concerns

  • The authors do not believe the work is likely to have negative societal impact.They caution that statistical methods require care in interpreting their results, including in high-stakes fields such as healthcare.Source: §10 · p. 8
  • NAPS prediction sets are statistical predictions and should be interpreted as such in high-stakes fields such as healthcare.Source: §10 · p. 8
  • The authors call for care when interpreting the results of statistical methods.Source: §10 · p. 8

A. Appendix

The appendix gives proof details for a coverage bound, documents dataset splits and evaluation-node selection, and reports model-training settings and computational overhead.

A.1. Proof of Lemma 5.1

  • The proof bounds conditional coverage using the counts of same-community and opposing-community neighbors, with opposing-community neighbors contributing a penalty.It also expresses expected coverage in terms of the random neighbor counts and derives a term-wise lower bound.Source: §A.1 · pp. 10–11

A.2. Dataset Details

  • The datasets are Flickr, Reddit2, and Amazon Computers, with original splits used for the first two and a constructed split for Amazon Computers.Evaluation is restricted to large connected components, selected using minimum 2-hop-neighbor counts; the resulting calibration-set sizes and dataset statistics are reported in Table 1.Source: §A.2 · p. 11

A.3. Model Training Details

  • All models used two GNN layers with hidden dimension 64, Adam at learning rate 0.1, dropout 0.5, and validation-based early stopping.The authors did not tune these parameters because they aimed to assess performance across architectures rather than optimize accuracy.Source: §A.3 · p. 11
  • Experiments took less than two hours on one machine, and the conformal procedure added trivial overhead relative to model fitting.NAPS was faster than APS because it used fewer calibration data points.Source: §A.3 · p. 11

Related papers

Loading 2211.14555v3…