# HeAD-CP: Heterophily-Aware Diffused Conformal Prediction Sets for Graph Neural Networks

arXiv: https://arxiv.org/abs/2607.25273 · HTML: https://mlsanity.com/paper/2607.25273/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 23 references that are in the map.
- First posted on arXiv 28 Jul 2026.

## Builds on (most cited first, 18 of 18)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Be Confident! Towards Trustworthy Graph Neural Networks via Confidence Calibration](https://mlsanity.com/paper/2109.14285/) (2021)
- [Graph Posterior Network: Bayesian Predictive Uncertainty for Node Classification](https://mlsanity.com/paper/2110.14012/) (2021)
- [Uncertainty Quantification over Graph with Conformalized Graph Neural Networks](https://mlsanity.com/paper/2305.14535/) (2023)
- [Similarity-Navigated Conformal Prediction for Graph Neural Networks](https://mlsanity.com/paper/2405.14303/) (2024)
- [Residual Reweighted Conformal Prediction for Graph Neural Networks](https://mlsanity.com/paper/2506.07854/) (2025)

## Built on by (most cited first, 2 of 2)

- [How Many Categories Are Enough? Distribution-Free Certification Limits for Few-Shot Anomaly Thresholds](https://mlsanity.com/paper/2610.00236/) (2026)
- [Valid for Free: Homophily-Gated Conformal Prediction for Training-Free Node Classification with Tabular Foundation Models](https://mlsanity.com/paper/2610.08564/) (2026)

## Abstract (arXiv)

Conformal prediction (CP) provides distribution-free uncertainty quantification, and its extension to graphs is an active research direction. Diffused Adaptive Prediction Sets (DAPS) is a widely used graph-aware diffusion baseline, propagating Adaptive Prediction Sets (APS) non-conformity scores along edges with a uniform coefficient λ. We identify a fundamental shortcoming of this design: the uniform low-pass diffusion presupposes graph homophily and proves detrimental on heterophilic graphs, enlarging the mean prediction-set size by up to 10.6% relative to plain APS. To mitigate this, we propose HeAD-CP, a family of node-wise diffusion variants whose coefficients are determined by a label-free local-homophily estimate derived from the GNN softmax. Three variants, namely signed-γ, edge-compatibility, and a DAPS-baseline-with-correction, are most effective at extreme heterophily, intermediate heterophily, and moderate-to-high homophily, respectively, and all preserve the marginal coverage guarantee. On ten benchmarks, the HeAD-CP family stays at or below plain APS on every dataset, while DAPS exceeds APS on six. The post-hoc oracle over the family improves over DAPS on 8/10 datasets at p<0.01 (paired Wilcoxon), with the largest gains on heterophilic graphs (10.3% on Texas); on the two homophilic datasets where DAPS still wins (CiteSeer, PubMed), it retains a marginal advantage of at most 0.002, statistically insignificant on CiteSeer (p=0.23). Designing a calibrated label-free selector that approaches this oracle is the main outstanding empirical question.