# Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 43 references that are in the map.
- First posted on arXiv 14 Oct 2024.

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

- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Neural Kernel Surface Reconstruction](https://mlsanity.com/paper/2305.19590/) (2023)
- [Neural Fields as Learnable Kernels for 3D Reconstruction](https://mlsanity.com/paper/2111.13674/) (2021)
- [Graph Kernels: A Survey](https://mlsanity.com/paper/1904.12218/) (2019)
- [Chefs' Random Tables: Non-Trigonometric Random Features](https://mlsanity.com/paper/2205.15317/) (2022)
- [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)

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

- [Computationally-efficient Graph Modeling with Refined Graph Random Features](https://mlsanity.com/paper/2510.07716/) (2025)
- [LGRPool: Hierarchical Graph Pooling Via Local-Global Regularisation](https://mlsanity.com/paper/2504.08530/) (2025)
- [SWING: Unlocking Implicit Graph Representations for Graph Random Features](https://mlsanity.com/paper/2602.12703/) (2026)

## Abstract (arXiv)

We present the first linear time complexity randomized algorithms for unbiased approximation of the celebrated family of general random walk kernels (RWKs) for sparse graphs. This includes both labelled and unlabelled instances. The previous fastest methods for general RWKs were of cubic time complexity and not applicable to labelled graphs. Our method samples dependent random walks to compute novel graph embeddings in ℝd whose dot product is equal to the true RWK in expectation. It does so without instantiating the direct product graph in memory, meaning we can scale to massive datasets that cannot be stored on a single machine. We derive exponential concentration bounds to prove that our estimator is sharp, and show that the ability to approximate general RWKs (rather than just special cases) unlocks efficient implicit graph kernel learning. Our method is up to 27× faster than its counterparts for efficient computation on large graphs and scales to graphs 128 × bigger than largest examples amenable to brute-force computation.