Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Choromanski, Krzysztof, Reid, Isaac, Sehanobish, Arijit, Dubey, Avinava
Format:	Preprint
Published:	2024
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Computationally-efficient Graph Modeling with Refined Graph Random Features
by: Choromanski, Krzysztof, et al.
Published: (2025)

SWING: Unlocking Implicit Graph Representations for Graph Random Features
by: Manenti, Alessandro, et al.
Published: (2026)

Scalable Neural Network Kernels
by: Sehanobish, Arijit, et al.
Published: (2023)

RelFlexformer: Efficient Attention 3D-Transformers for Integrable Relative Positional Encodings
by: Kim, Byeongchan, et al.
Published: (2026)

Towards Scalable Exact Machine Unlearning Using Parameter-Efficient Fine-Tuning
by: Chowdhury, Somnath Basu Roy, et al.
Published: (2024)

General Graph Random Features
by: Reid, Isaac, et al.
Published: (2023)

Repelling Random Walks
by: Reid, Isaac, et al.
Published: (2023)

Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers
by: Choromanski, Krzysztof, et al.
Published: (2024)

Structured Unrestricted-Rank Matrices for Parameter Efficient Fine-tuning
by: Sehanobish, Arijit, et al.
Published: (2024)

Rotary Position Encodings for Graphs
by: Reid, Isaac, et al.
Published: (2025)

Graph Random Features for Scalable Gaussian Processes
by: Zhang, Matthew, et al.
Published: (2025)

Linear Transformer Topological Masking with Graph Random Features
by: Reid, Isaac, et al.
Published: (2024)

EUGens: Efficient, Unified, and General Dense Layers
by: Kim, Sang Min, et al.
Published: (2026)

EUGens: Efficient, Unified, and General Dense Layers
by: Kim, Sang Min, et al.
Published: (2024)

Variance-Reducing Couplings for Random Features
by: Reid, Isaac, et al.
Published: (2024)

Cross-device Zero-shot Label Transfer via Alignment of Time Series Foundation Model Embeddings
by: Ravindra, Neal G., et al.
Published: (2025)

Not How Many, But Which: Parameter Placement in Low-Rank Adaptation
by: Sehanobish, Arijit, et al.
Published: (2026)

SLAY: Geometry-Aware Spherical Linearized Attention with Yat-Kernel
by: Luna, Jose Miguel, et al.
Published: (2026)

Manifold Random Features
by: Parashar, Ananya, et al.
Published: (2026)

Distributed Graph Embedding with Information-Oriented Random Walks
by: Fang, Peng, et al.
Published: (2023)

A Survey on Recent Random Walk-based Methods for Embedding Knowledge Graphs
by: Bozorgi, Elika, et al.
Published: (2024)

GraphWeave: Interpretable and Robust Graph Generation via Random Walk Trajectories
by: Nandakumar, Rahul, et al.
Published: (2025)

Learning a Fourier Transform for Linear Relative Positional Encodings in Transformers
by: Choromanski, Krzysztof Marcin, et al.
Published: (2023)

Flock: A Knowledge Graph Foundation Model via Learning on Random Walks
by: Kim, Jinwoo, et al.
Published: (2025)

Random Walk Guided Hyperbolic Graph Distillation
by: Long, Yunbo, et al.
Published: (2025)

Revisiting Random Walks for Learning on Graphs
by: Kim, Jinwoo, et al.
Published: (2024)

Descriptive Kernel Convolution Network with Improved Random Walk Kernel
by: Lee, Meng-Chieh, et al.
Published: (2024)

Rethinking Graph Out-Of-Distribution Generalization: A Learnable Random Walk Perspective
by: Sun, Henan, et al.
Published: (2025)

Random Walk Diffusion for Efficient Large-Scale Graph Generation
by: Bernecker, Tobias, et al.
Published: (2024)

Surrogate Interpretable Graph for Random Decision Forests
by: Dubey, Akshat, et al.
Published: (2025)

Learning Long Range Dependencies on Graphs via Random Walks
by: Chen, Dexiong, et al.
Published: (2024)

Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs
by: Choromanski, Krzysztof, et al.
Published: (2026)

Optimality of Message-Passing Architectures for Sparse Graphs
by: Baranwal, Aseem, et al.
Published: (2023)

Graph Neural Networks with Feature and Structure Aware Random Walk
by: Zhuo, Wei, et al.
Published: (2021)

Karyotype AI for Precision Oncology
by: Shamsi, Zahra, et al.
Published: (2022)

Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks
by: Maurya, Sunil Kumar, et al.
Published: (2026)

Disentangled Graph Representation Based on Substructure-Aware Graph Optimal Matching Kernel Convolutional Networks
by: Wang, Mao, et al.
Published: (2025)

Hub-aware Random Walk Graph Embedding Methods for Classification
by: Tomčić, Aleksandar, et al.
Published: (2022)

Random Wavelet Features for Graph Kernel Machines
by: de Bassompierre, Valentin, et al.
Published: (2026)

Generating Robust Counterfactual Witnesses for Graph Neural Networks
by: Qiu, Dazhuo, et al.
Published: (2024)