Quasi-Monte Carlo Graph Random Features
Isaac Reid Krzysztof Choromanski Adrian Weller
We present a novel mechanism to improve the accuracy of the
recently-introduced class of graph random features (GRFs). Our method induces
negative correlations between the lengths of the algorithm's random walks by
imposing antithetic termination: a procedure to sample more diverse random
walks which may be of independent interest. It has a trivial drop-in
implementation. We derive strong theoretical guarantees on the properties of
these quasi-Monte Carlo GRFs (q-GRFs), proving that they yield lower-variance
estimators of the 2-regularised Laplacian kernel under mild conditions.
Remarkably, our results hold for any graph topology. We demonstrate empirical
accuracy improvements on a variety of tasks including a new practical
application: time-efficient approximation of the graph diffusion process. To
our knowledge, q-GRFs constitute the first rigorously studied quasi-Monte Carlo
scheme for kernels defined on combinatorial objects, inviting new research on
correlations between graph random walks.