# Graph Random Features for Scalable Gaussian Processes

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 50 references that are in the map.
- First posted on arXiv 3 Sep 2025.

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

- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [GPflow: A Gaussian process library using TensorFlow](https://mlsanity.com/paper/1610.08733/) (2016)
- [Efficiently Sampling Functions from Gaussian Process Posteriors](https://mlsanity.com/paper/2002.09309/) (2020)
- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Mat'ern Gaussian Processes on Graphs](https://mlsanity.com/paper/2010.15538/) (2020)
- [Pathwise Conditioning of Gaussian Processes](https://mlsanity.com/paper/2011.04026/) (2020)
- [A Framework for Interdomain and Multioutput Gaussian Processes](https://mlsanity.com/paper/2003.01115/) (2020)
- [From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers](https://mlsanity.com/paper/2107.07999/) (2021)
- [A Tutorial on Sparse Gaussian Processes and Variational Inference](https://mlsanity.com/paper/2012.13962/) (2020)
- [Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent](https://mlsanity.com/paper/2306.11589/) (2023)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [Stochastic Gradient Descent for Gaussian Processes Done Right](https://mlsanity.com/paper/2310.20581/) (2023)
- [When are Iterative Gaussian Processes Reliably Accurate?](https://mlsanity.com/paper/2112.15246/) (2021)
- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [General Graph Random Features](https://mlsanity.com/paper/2310.04859/) (2023)
- [Scaling Gaussian Processes for Learning Curve Prediction via Latent Kronecker Structure](https://mlsanity.com/paper/2410.09239/) (2024)
- [Intrinsic Gaussian Vector Fields on Manifolds](https://mlsanity.com/paper/2310.18824/) (2023)
- [Bayesian Optimisation of Functions on Graphs](https://mlsanity.com/paper/2306.05304/) (2023)
- [Linear Transformer Topological Masking with Graph Random Features](https://mlsanity.com/paper/2410.03462/) (2024)
- [Improving Linear System Solvers for Hyperparameter Optimisation in Iterative Gaussian Processes](https://mlsanity.com/paper/2405.18457/) (2024)
- [Scalable Gaussian Processes with Latent Kronecker Structure](https://mlsanity.com/paper/2506.06895/) (2025)
- [Implicit Manifold Gaussian Process Regression](https://mlsanity.com/paper/2310.19390/) (2023)
- [Variance-Reducing Couplings for Random Features](https://mlsanity.com/paper/2405.16541/) (2024)
- [Residual Deep Gaussian Processes on Manifolds](https://mlsanity.com/paper/2411.00161/) (2024)

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

- [Scalable Random Wavelet Features: Efficient Non-Stationary Kernel Approximation with Convergence Guarantees](https://mlsanity.com/paper/2602.00987/) (2026)
- [Conformalized Gaussian processes for online uncertainty quantification over graphs](https://mlsanity.com/paper/2510.06181/) (2025)
- [Manifold Random Features](https://mlsanity.com/paper/2602.03797/) (2026)
- [SWING: Unlocking Implicit Graph Representations for Graph Random Features](https://mlsanity.com/paper/2602.12703/) (2026)
- [Structure-Adaptive Tree Field Integrators](https://mlsanity.com/paper/2609.34025/) (2026)

## Abstract (arXiv)

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 O(N3/2) time complexity with respect to the number of nodes N, compared to O(N3) for exact kernels. Substantial wall-clock speedups and memory savings unlock Bayesian optimisation on graphs with over 106 nodes on a single computer chip, whilst preserving competitive performance.