arXiv preprint ·
Monte Carlo Random Walk Kernel
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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)$ time for $m$ 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
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
PhysicsNeMo-Mesh: GPU-Native Meshes and Simulation Cases for Physics AI
MUON-RT Reusing the Teacher's Trajectory for Momentum-Free Muon for LLM Self-Distillation
Tactus: Tactile & Pose Sensing Glove for Natural Dexterity Data Collection
Differential rank preservation manifold learning
PALATE: Pretrained Autoregressive LATent Embeddings
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.