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

arXiv:2410.10368v3 Announce Type: replace Abstract: We present the first linear time complexity randomized algorithms for unbiased approximation of the celebrated family of general random walk kernels (RWKs) for sparse graphs. This includes both labelled and unlabelled instances. The previous fastest methods for general RWKs were of cubic time complexity and not applicable to labelled graphs. Our method samples dependent random walks to compute novel graph embeddings in R^d whose dot product is equal to the true RWK in expectation. It does so without instantiating the direct product graph in memory, meaning we can scale to massive datasets that cannot be stored on a single machine. We derive exponential concentration bounds to prove that our estimator is sharp, and show that the ability to approximate general RWKs (rather than just special cases) unlocks efficient implicit graph kernel learning. Our method is up to mathbf{27imes} faster than its counterparts for efficient computation on large graphs and scales to graphs mathbf{128 imes} bigger than largest examples amenable to brute-force computation.

Related

• SWING: Unlocking Implicit Graph Representations for Graph Random Features
• A Graphop Analysis of Graph Neural Networks on Sparse Graphs: Generalization and Universal Approximation
• Optimal differentially private kernel learning with random projection
• GIST: Gauge-Invariant Spectral Transformers for Scalable Graph Neural Operators

Source: arXiv cs.LG | 2026-08-27