cs.LGOct 29, 2026

Monte Carlo Random Walk Kernel

Authors: Arslan Iamaletdinov, Elfat Sabitov, Konstantin Sorokin

Organizations: HSE University

Abstract

We introduce the Monte Carlo Random Walk Kernel (MCRWK), an estimator whose per-pair cost is independent of graph size and derived directly from the random walk kernel (RWK) expansion. By normalizing the kernel coefficients, MCRWK samples a shared walk length and estimates its contribution using random walks on the input graphs. This gives a simple way to approximate RWK without constructing the product graph. For a fixed expected walk length and efficient neighbor sampling, each pairwise estimate takes O(m)O(m) time for mm Monte Carlo samples, allowing the sample budget to control the trade-off between runtime and accuracy. We evaluate MCRWK against Graph Voyagers and classical RWK methods on synthetic and real graph datasets. In the reported experiments on large synthetic graphs, MCRWK is faster than Graph Voyagers and, at matched runtime, more accurate. It also has the lowest Gram-matrix runtime on the five real datasets studied. Code and experiments are available at https://github.com/arslan-yam/random_walk_kernels_computations

Figures & tables

Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Computationally-efficient Graph Modeling with Refined Graph Random Features

    Oct 9, 2025Krzysztof Choromanski, Avinava Dubey, Arijit Sehanobish +1Graph Representation LearningRandomized Sketching

  2. node2vec or triangle-biased random walks: stationarity, regularity & recurrence

    Apr 15, 2026Luca Avena, Gianmarco Bet, Lars Schroeder +1Markov ModelsGraph Embedding

  3. Random Wavelet Features for Graph Kernel Machines

    Feb 17, 2026Valentin de Bassompierre, Jean-Charles Delvenne, Laurent JacquesGraph Representation LearningGraph Embedding