# Taming graph kernels with random features

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 47 references that are in the map.
- First posted on arXiv 29 Apr 2023.

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

- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [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)
- [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)
- [From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers](https://mlsanity.com/paper/2107.07999/) (2021)
- [Reproducing Kernel Hilbert Space, Mercer's Theorem, Eigenfunctions, Nystr"om Method, and Use of Kernels in Machine Learning: Tutorial and Survey](https://mlsanity.com/paper/2106.08443/) (2021)
- [Hybrid Random Features](https://mlsanity.com/paper/2110.04367/) (2021)
- [Chefs' Random Tables: Non-Trigonometric Random Features](https://mlsanity.com/paper/2205.15317/) (2022)
- [A General Framework for Estimating Graphlet Statistics via Random Walk](https://mlsanity.com/paper/1603.07504/) (2016)
- [Scalable Global Alignment Graph Kernel Using Random Features: From Node Embedding to Graph Embedding](https://mlsanity.com/paper/1911.11119/) (2019)
- [Demystifying Orthogonal Monte Carlo and Beyond](https://mlsanity.com/paper/2005.13590/) (2020)
- [A Survey on Subgraph Counting: Concepts, Algorithms and Applications to Network Motifs and Graphlets](https://mlsanity.com/paper/1910.13011/) (2019)
- [On the Emergence of Shortest Paths by Reinforced Random Walks](https://mlsanity.com/paper/1605.02619/) (2016)

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

- [What Can We Learn from State Space Models for Machine Learning on Graphs?](https://mlsanity.com/paper/2406.05815/) (2024)
- [Expectation-Complete Graph Representations with Homomorphisms](https://mlsanity.com/paper/2306.05838/) (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)
- [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)
- [Graph Random Features for Scalable Gaussian Processes](https://mlsanity.com/paper/2509.03691/) (2025)
- [Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs](https://mlsanity.com/paper/2410.10368/) (2024)
- [Local Graph Clustering with Noisy Labels](https://mlsanity.com/paper/2310.08031/) (2023)
- [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)
- [Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks](https://mlsanity.com/paper/2511.03824/) (2025)
- [Manifold Random Features](https://mlsanity.com/paper/2602.03797/) (2026)
- [Heating Up Quasi-Monte Carlo Graph Random Features: A Diffusion Kernel Perspective](https://mlsanity.com/paper/2410.08389/) (2024)
- [SWING: Unlocking Implicit Graph Representations for Graph Random Features](https://mlsanity.com/paper/2602.12703/) (2026)
- [Random Wavelet Features for Graph Kernel Machines](https://mlsanity.com/paper/2602.15711/) (2026)

## Abstract (arXiv)

We introduce in this paper the mechanism of graph random features (GRFs). GRFs can be used to construct unbiased randomized estimators of several important kernels defined on graphs' nodes, in particular the regularized Laplacian kernel. As regular RFs for non-graph kernels, they provide means to scale up kernel methods defined on graphs to larger networks. Importantly, they give substantial computational gains also for smaller graphs, while applied in downstream applications. Consequently, GRFs address the notoriously difficult problem of cubic (in the number of the nodes of the graph) time complexity of graph kernels algorithms. We provide a detailed theoretical analysis of GRFs and an extensive empirical evaluation: from speed tests, through Frobenius relative error analysis to kmeans graph-clustering with graph kernels. We show that the computation of GRFs admits an embarrassingly simple distributed algorithm that can be applied if the graph under consideration needs to be split across several machines. We also introduce a (still unbiased) quasi Monte Carlo variant of GRFs, q-GRFs, relying on the so-called reinforced random walks, that might be used to optimize the variance of GRFs. As a byproduct, we obtain a novel approach to solve certain classes of linear equations with positive and symmetric matrices.