mlsanityData to 14 Oct 2026

Graph Random Features for Scalable Gaussian Processes

arXiv 2509.03691 ↗First posted 3 Sep 2025cs.LGcited by 5

Not on the map. Why?

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.

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

26 of 50 references.

References · 26

  1. 2018GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Accelerationcited by 609
  2. 2017A Tutorial on Thompson Samplingcited by 433
  3. 2016GPflow: A Gaussian process library using TensorFlowcited by 140
  4. 2020Efficiently Sampling Functions from Gaussian Process Posteriorscited by 127
  5. 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
  6. 2016Orthogonal Random Featurescited by 91
  7. 2020Mat'ern Gaussian Processes on Graphscited by 66
  8. 2020Pathwise Conditioning of Gaussian Processescited by 64
  9. 2020A Framework for Interdomain and Multioutput Gaussian Processescited by 48
  10. 2021From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformerscited by 38
  11. 2020A Tutorial on Sparse Gaussian Processes and Variational Inferencecited by 31
  12. 2023Sampling from Gaussian Process Posteriors using Stochastic Gradient Descentcited by 27
14 more
  1. 2023Taming graph kernels with random featurescited by 17
  2. 2023Stochastic Gradient Descent for Gaussian Processes Done Rightcited by 17
  3. 2021When are Iterative Gaussian Processes Reliably Accurate?cited by 12
  4. 2021An Introduction to Johnson-Lindenstrauss Transformscited by 11
  5. 2023General Graph Random Featurescited by 10
  6. 2024Scaling Gaussian Processes for Learning Curve Prediction via Latent Kronecker Structurecited by 10
  7. 2023Intrinsic Gaussian Vector Fields on Manifoldscited by 8
  8. 2023Bayesian Optimisation of Functions on Graphscited by 7
  9. 2024Linear Transformer Topological Masking with Graph Random Featurescited by 7
  10. 2024Improving Linear System Solvers for Hyperparameter Optimisation in Iterative Gaussian Processescited by 5
  11. 2025Scalable Gaussian Processes with Latent Kronecker Structurecited by 5
  12. 2023Implicit Manifold Gaussian Process Regressioncited by 4
  13. 2024Variance-Reducing Couplings for Random Featurescited by 2
  14. 2024Residual Deep Gaussian Processes on Manifoldscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 4.

5 papers.

  1. 2026Scalable Random Wavelet Features: Efficient Non-Stationary Kernel Approximation with Convergence Guaranteescited by 2
  2. 2025Conformalized Gaussian processes for online uncertainty quantification over graphscited by 1
  3. 2026Manifold Random Featurescited by 1
  4. 2026SWING: Unlocking Implicit Graph Representations for Graph Random Featurescited by 0
  5. 2026Structure-Adaptive Tree Field Integratorscited by 0