Computationally-efficient Graph Modeling with Refined Graph Random Features

Krzysztof Marcin Choromanski, Kumar Avinava Dubey, Arijit Sehanobish, Isaac Reid
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:20494-20516, 2026.

Abstract

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 approximation accuracy of graph kernels, without incurring extra computational cost. We provide empirical evaluations to showcase our claims and complement our results with theoretical analysis.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-choromanski26a, title = {Computationally-efficient Graph Modeling with Refined Graph Random Features}, author = {Choromanski, Krzysztof Marcin and Dubey, Kumar Avinava and Sehanobish, Arijit and Reid, Isaac}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {20494--20516}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/choromanski26a/choromanski26a.pdf}, url = {https://proceedings.mlr.press/v306/choromanski26a.html}, abstract = {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 approximation accuracy of graph kernels, without incurring extra computational cost. We provide empirical evaluations to showcase our claims and complement our results with theoretical analysis.} }
Endnote
%0 Conference Paper %T Computationally-efficient Graph Modeling with Refined Graph Random Features %A Krzysztof Marcin Choromanski %A Kumar Avinava Dubey %A Arijit Sehanobish %A Isaac Reid %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-choromanski26a %I PMLR %P 20494--20516 %U https://proceedings.mlr.press/v306/choromanski26a.html %V 306 %X 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 approximation accuracy of graph kernels, without incurring extra computational cost. We provide empirical evaluations to showcase our claims and complement our results with theoretical analysis.
APA
Choromanski, K.M., Dubey, K.A., Sehanobish, A. & Reid, I.. (2026). Computationally-efficient Graph Modeling with Refined Graph Random Features. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:20494-20516 Available from https://proceedings.mlr.press/v306/choromanski26a.html.

Related Material