# Conformalized Gaussian processes for online uncertainty quantification over graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 30 references that are in the map.
- First posted on arXiv 7 Oct 2025.

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

- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles](https://mlsanity.com/paper/1612.01474/) (2016)
- [Can You Trust Your Model's Uncertainty? Evaluating Predictive Uncertainty Under Dataset Shift](https://mlsanity.com/paper/1906.02530/) (2019)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [When Gaussian Process Meets Big Data: A Review of Scalable GPs](https://mlsanity.com/paper/1807.01065/) (2018)
- [Bayesian graph convolutional neural networks for semi-supervised classification](https://mlsanity.com/paper/1811.11103/) (2018)
- [Uncertainty Quantification over Graph with Conformalized Graph Neural Networks](https://mlsanity.com/paper/2305.14535/) (2023)
- [Mat'ern Gaussian Processes on Graphs](https://mlsanity.com/paper/2010.15538/) (2020)
- [Online conformal prediction with decaying step sizes](https://mlsanity.com/paper/2402.01139/) (2024)
- [Bayesian Semi-supervised Learning with Graph Gaussian Processes](https://mlsanity.com/paper/1809.04379/) (2018)
- [Distribution Free Prediction Sets for Node Classification](https://mlsanity.com/paper/2211.14555/) (2022)
- [Gaussian Processes on Graphs via Spectral Kernel Learning](https://mlsanity.com/paper/2006.07361/) (2020)
- [Graph Convolutional Gaussian Processes](https://mlsanity.com/paper/1905.05739/) (2019)
- [Variational Learning on Aggregate Outputs with Gaussian Processes](https://mlsanity.com/paper/1805.08463/) (2018)
- [Discretized conformal prediction for efficient distribution-free inference](https://mlsanity.com/paper/1709.06233/) (2017)
- [Bayesian Optimisation of Functions on Graphs](https://mlsanity.com/paper/2306.05304/) (2023)
- [Similarity-Navigated Conformal Prediction for Graph Neural Networks](https://mlsanity.com/paper/2405.14303/) (2024)
- [Graph Random Features for Scalable Gaussian Processes](https://mlsanity.com/paper/2509.03691/) (2025)
- [Online scalable Gaussian processes with conformal prediction for guaranteed coverage](https://mlsanity.com/paper/2410.05444/) (2024)

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

- [Online Bayesian Node Classification on Inductive Graphs under Distribution Shift](https://mlsanity.com/paper/2609.13655/) (2026)

## Abstract (arXiv)

Uncertainty quantification (UQ) over graphs arises in a number of safety-critical applications in network science. The Gaussian process (GP), as a classical Bayesian framework for UQ, has been developed to handle graph-structured data by devising topology-aware kernel functions. However, such GP-based approaches are limited not only by the prohibitive computational complexity, but also the strict modeling assumptions that might yield poor coverage, especially with labels arriving on the fly. To effect scalability, we devise a novel graph-aware parametric GP model by leveraging the random feature (RF)-based kernel approximation, which is amenable to efficient recursive Bayesian model updates. To further allow for adaptivity, an ensemble of graph-aware RF-based scalable GPs have been leveraged, with per-GP weight adapted to data arriving incrementally. To ensure valid coverage with robustness to model mis-specification, we wed the GP-based set predictors with the online conformal prediction framework, which post-processes the prediction sets using adaptive thresholds. Experimental results the proposed method yields improved coverage and efficient prediction sets over existing baselines by adaptively ensembling the GP models and setting the key threshold parameters in CP.