# Computationally-efficient Graph Modeling with Refined Graph Random Features

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 51 references that are in the map.
- First posted on arXiv 9 Oct 2025.

## Builds on (most cited first, 30 of 31)

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Thingi10K: A Dataset of 10,000 3D-Printing Models](https://mlsanity.com/paper/1605.04797/) (2016)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [A Survey of Graph Neural Networks for Recommender Systems: Challenges, Methods, and Directions](https://mlsanity.com/paper/2109.12843/) (2021)
- [Graph Kernels: A Survey](https://mlsanity.com/paper/1904.12218/) (2019)
- [Towards Self-Interpretable Graph-Level Anomaly Detection](https://mlsanity.com/paper/2310.16520/) (2023)
- [Graph Anomaly Detection with Graph Neural Networks: Current Status and Challenges](https://mlsanity.com/paper/2209.14930/) (2022)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [SpaceGNN: Multi-Space Graph Neural Network for Node Anomaly Detection with Extremely Limited Labels](https://mlsanity.com/paper/2502.03201/) (2025)
- [A Simple Baseline Algorithm for Graph Classification](https://mlsanity.com/paper/1810.09155/) (2018)
- [EquiPocket: an E(3)-Equivariant Geometric Graph Neural Network for Ligand Binding Site Prediction](https://mlsanity.com/paper/2302.12177/) (2023)
- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [General Graph Random Features](https://mlsanity.com/paper/2310.04859/) (2023)
- [Quasi-Monte Carlo Graph Random Features](https://mlsanity.com/paper/2305.12470/) (2023)
- [DiffGAD: A Diffusion-based Unsupervised Graph Anomaly Detector](https://mlsanity.com/paper/2410.06549/) (2024)
- [Scalable Global Alignment Graph Kernel Using Random Features: From Node Embedding to Graph Embedding](https://mlsanity.com/paper/1911.11119/) (2019)
- [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)
- [Molecule Graph Networks with Many-body Equivariant Interactions](https://mlsanity.com/paper/2406.13265/) (2024)
- [Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers](https://mlsanity.com/paper/2406.15881/) (2024)
- [Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs](https://mlsanity.com/paper/2410.10368/) (2024)
- [Hgformer: Hyperbolic Graph Transformer for Recommendation](https://mlsanity.com/paper/2502.15693/) (2024)

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

- [Manifold Random Features](https://mlsanity.com/paper/2602.03797/) (2026)
- [SWING: Unlocking Implicit Graph Representations for Graph Random Features](https://mlsanity.com/paper/2602.12703/) (2026)

## Abstract (arXiv)

We propose refined GRFs (GRFs++), a new class of Graph Random Features (GRFs) for efficient and accurate computations involving kernels defined on the nodes of a graph. GRFs++ resolve some of the long-standing limitations of regular GRFs, including difficulty modeling relationships between more distant nodes. They reduce dependence on sampling long graph random walks via a novel walk-stitching technique, concatenating several shorter walks without breaking unbiasedness. By applying these techniques, GRFs++ inherit the approximation quality provided by longer walks but with greater efficiency, trading sequential, inefficient sampling of a long walk for parallel computation of short walks and matrix-matrix multiplication. Furthermore, GRFs++ extend the simplistic GRFs walk termination mechanism (Bernoulli schemes with fixed halting probabilities) to a broader class of strategies, applying general distributions on the walks' lengths. This improves the approximation accuracy of graph kernels, without incurring extra computational cost. We provide empirical evaluations to showcase all our claims and complement our results with theoretical analysis.