{"ID":2875169,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.03691","arxiv_id":"2509.03691","title":"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 $O(N^{3/2})$ time complexity with respect to the number of nodes $N$, compared to $O(N^3)$ for exact kernels. Substantial wall-clock speedups and memory savings unlock Bayesian optimisation on graphs with over $10^6$ nodes on a single computer chip, whilst preserving competitive performance.","short_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 $O(N^{3/2})$ time complexity with respect to the number of nod...","url_abs":"https://arxiv.org/abs/2509.03691","url_pdf":"https://arxiv.org/pdf/2509.03691v2","authors":"[\"Matthew Zhang\",\"Jihao Andreas Lin\",\"Krzysztof Choromanski\",\"Adrian Weller\",\"Richard E. Turner\",\"Isaac Reid\"]","published":"2025-09-03T20:13:23Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[]","has_code":false}