Graph Random Features for Scalable Gaussian Processes
This work addresses the computational bottleneck for Bayesian inference on large graphs, making it more accessible for applications like network analysis or recommendation systems, though it is incremental as it builds on existing random feature methods.
The paper tackles the problem of scaling Gaussian processes to large graphs by introducing graph random features, achieving a time complexity reduction from O(N^3) to O(N^{3/2}) and enabling Bayesian optimization on graphs with over 10^6 nodes on a single chip while maintaining competitive performance.
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.