# Heating Up Quasi-Monte Carlo Graph Random Features: A Diffusion Kernel Perspective

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 14 references that are in the map.
- First posted on arXiv 10 Oct 2024.

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

- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [General Graph Random Features](https://mlsanity.com/paper/2310.04859/) (2023)
- [Quasi-Monte Carlo Graph Random Features](https://mlsanity.com/paper/2305.12470/) (2023)
- [Repelling Random Walks](https://mlsanity.com/paper/2310.04854/) (2023)

## Abstract (arXiv)

We build upon a recently introduced class of quasi-graph random features (q-GRFs), which have demonstrated the ability to yield lower variance estimators of the 2-regularized Laplacian kernel (Choromanski 2023). Our research investigates whether similar results can be achieved with alternative kernel functions, specifically the Diffusion (or Heat), Mat'ern, and Inverse Cosine kernels. We find that the Diffusion kernel performs most similarly to the 2-regularized Laplacian, and we further explore graph types that benefit from the previously established antithetic termination procedure. Specifically, we explore ErdHos-R'enyi and Barab'asi-Albert random graph models, Binary Trees, and Ladder graphs, with the goal of identifying combinations of specific kernel and graph type that benefit from antithetic termination. We assert that q-GRFs achieve lower variance estimators of the Diffusion (or Heat) kernel on Ladder graphs. However, the number of rungs on the Ladder graphs impacts the algorithm's performance; further theoretical results supporting our experimentation are forthcoming. This work builds upon some of the earliest Quasi-Monte Carlo methods for kernels defined on combinatorial objects, paving the way for kernel-based learning algorithms and future real-world applications in various domains.