2026
Graph Random Features for Scalable Gaussian Processes
Matthew Zhang, Jihao Andreas Lin, Krzysztof Marcin Choromanski, Adrian Weller, Richard E. Turner, Isaac Reid
ICLR 2026poster
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 wit…