Graph Random Features for Scalable Gaussian Processes
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.
Cite
Text
Zhang et al. "Graph Random Features for Scalable Gaussian Processes." International Conference on Learning Representations, 2026.Markdown
[Zhang et al. "Graph Random Features for Scalable Gaussian Processes." International Conference on Learning Representations, 2026.](https://mlanthology.org/iclr/2026/zhang2026iclr-graph/)BibTeX
@inproceedings{zhang2026iclr-graph,
title = {{Graph Random Features for Scalable Gaussian Processes}},
author = {Zhang, Matthew and Lin, Jihao Andreas and Choromanski, Krzysztof Marcin and Weller, Adrian and Turner, Richard E. and Reid, Isaac},
booktitle = {International Conference on Learning Representations},
year = {2026},
url = {https://mlanthology.org/iclr/2026/zhang2026iclr-graph/}
}