# Quasi-Monte Carlo Graph Random Features

arXiv: https://arxiv.org/abs/2305.12470 · HTML: https://mlsanity.com/paper/2305.12470/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 58 references that are in the map.
- First posted on arXiv 21 May 2023.

## Builds on (most cited first, 15 of 15)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Energy and Policy Considerations for Deep Learning in NLP](https://mlsanity.com/paper/1906.02243/) (2019)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings](https://mlsanity.com/paper/1703.00864/) (2017)
- [Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels](https://mlsanity.com/paper/1412.8293/) (2014)
- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [A General Framework for Estimating Graphlet Statistics via Random Walk](https://mlsanity.com/paper/1603.07504/) (2016)
- [Simplex Random Features](https://mlsanity.com/paper/2301.13856/) (2023)
- [Scalable Global Alignment Graph Kernel Using Random Features: From Node Embedding to Graph Embedding](https://mlsanity.com/paper/1911.11119/) (2019)
- [Learning Manifold Implicitly via Explicit Heat-Kernel Learning](https://mlsanity.com/paper/2010.01761/) (2020)

## Built on by (most cited first, 9 of 9)

- [What Can We Learn from State Space Models for Machine Learning on Graphs?](https://mlsanity.com/paper/2406.05815/) (2024)
- [General Graph Random Features](https://mlsanity.com/paper/2310.04859/) (2023)
- [Linear Transformer Topological Masking with Graph Random Features](https://mlsanity.com/paper/2410.03462/) (2024)
- [Repelling Random Walks](https://mlsanity.com/paper/2310.04854/) (2023)
- [Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs](https://mlsanity.com/paper/2410.10368/) (2024)
- [Variance-Reducing Couplings for Random Features](https://mlsanity.com/paper/2405.16541/) (2024)
- [Rapid training of Hamiltonian graph networks using random features](https://mlsanity.com/paper/2506.06558/) (2025)
- [Computationally-efficient Graph Modeling with Refined Graph Random Features](https://mlsanity.com/paper/2510.07716/) (2025)
- [Heating Up Quasi-Monte Carlo Graph Random Features: A Diffusion Kernel Perspective](https://mlsanity.com/paper/2410.08389/) (2024)

## Abstract (arXiv)

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.