ICLR 2026poster0 citations
Graph Random Features for Scalable Gaussian Processes
Matthew Zhang, Jihao Andreas Lin, Krzysztof Marcin Choromanski, Adrian Weller, Richard E. Turner, Isaac Reid
Abstract
We study the application of graph random features (GRFs) – a recently-introduced stochastic estimator of graph node kernels – to scalable Gaussian processes on discrete input spaces. We prove that (under mild assumptions) Bayesian inference with GRFs enjoys $\mathcal{O}(N^{3/2})$ time complexity with respect to the number of nodes $N$, with probabilistic accuracy guarantees. In contrast, exact kernels generally incur $\mathcal{O}(N^{3})$. Wall-clock speedups and memory savings unlock Bayesian optimisation with over 1M graph nodes on a single computer chip, whilst preserving competitive performance.
kernelsgraphsGaussian processesMonte Carloinference
BibTeX
@inproceedings{
zhang2026graph,
title={Graph Random Features for Scalable Gaussian Processes},
author={Matthew Zhang and Jihao Andreas Lin and Krzysztof Marcin Choromanski and Adrian Weller and Richard E. Turner and Isaac Reid},
booktitle={The Fourteenth International Conference on Learning Representations},
year={2026},
url={https://openreview.net/forum?id=89SQfLguNn}
}