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 27× faster than its counterparts for efficient computation on large graphs and scales to graphs 128× bigger than largest examples amenable to brute-force computation.
Introduction: The Computational Tax of Graph Similarity
Graph kernels are fundamental to structural machine learning, providing a measure of similarity between networks. Among these, Random Walk Kernels (RWKs) are considered a gold standard due to their expressivity. However, they have historically been limited by a significant "computational tax." Comparing two graphs with $N$ nodes using traditional methods often requires $O(N^3)$ or even $O(N^6)$ time, rendering them impractical for the massive sparse graphs common in social networks and bioinformatics.
The Challenge: The Direct Product Graph Bottleneck
The primary obstacle in computing RWKs is the requirement to construct or simulate a Direct Product Graph. To determine the number of shared walks between two graphs, one must traditionally conceptualize a "super-graph" where every node represents a pair of nodes from the original graphs. For two graphs with 1,000 nodes each, the resulting product graph contains 1,000,000 nodes. While specific "geometric" variants of these kernels have seen optimization, general RWKs—which support vertex labels and flexible walk length weightings—remained constrained by cubic complexity.
Graph Voyagers (GVoys): The $O(N)$ Solution
A collaboration between researchers at Google DeepMind, Cambridge, and Columbia introduces Graph Voyagers (GVoys), the first randomized algorithm to achieve linear time complexity $O(N)$ for approximating general RWKs on sparse graphs. GVoys bypasses the explicit construction of the product graph by utilizing a technique called Graph Random Features (GRFs).
The core innovation lies in how the algorithm handles randomness:
- Independent Walks with Shared Randomness: Random walks are simulated on Graph A and Graph B separately.
- Coupling Variables: To ensure these independent simulations accurately represent a shared walk on a product graph, the authors introduce shared random variables:
- $g$-variables: Act as filters to ensure only walks of identical lengths contribute to the similarity score. The authors prove that Rademacher variables (randomly choosing +1 or -1) are optimal for minimizing variance.
- $z$-variables: Handle vertex labels, ensuring a walk is only counted if the sequence of labels (e.g., atom types in a molecule) matches exactly between the two graphs.
- Unbiased Embeddings: This process generates low-dimensional vector embeddings for each graph. The similarity between two graphs is then computed as the simple dot product of these vectors. Crucially, this estimator is unbiased, meaning its expected value is exactly equal to the true kernel value.
Empirical Performance and Scalability
The researchers evaluated GVoys across standard benchmarks, including bioinformatics (PROTEINS, D&D), small molecules (MUTAG, NCI1), and large-scale synthetic graphs.
Key results from the evaluation include:
- Speed and Scale: GVoys is up to 27x faster than previous fixed-point iteration methods. It successfully processed graphs with over 16,000 nodes—a scale where baseline methods either timed out (exceeding 24 hours) or ran out of memory.
- Accuracy and Regularization: In classification tasks, GVoys often outperformed exact RWKs. The authors suggest the stochastic nature of the approximation may act as a form of regularization against structural noise.
- Implicit Kernel Learning: The efficiency of GVoys enables Implicit Graph Kernel Learning. Instead of manually selecting kernel parameters, researchers can treat walk-length weights as learnable variables, optimizing them for specific tasks. On the MUTAG dataset, this approach yielded an 8.5% relative improvement over standard geometric RWKs.
Conclusion
Graph Voyagers represent a significant leap in graph similarity computation, moving from cubic to linear time complexity for general RWKs. By emulating product graph behavior through coupled randomness, GVoys allows for structural analysis on a scale previously thought impossible. Future research may extend this framework to directed graphs or integrate these structural embeddings directly into deep learning architectures.
Reference: Krzysztof Choromanski, et al. "Optimal Time Complexity Algorithms for Computing General RWKs on Sparse Graphs." AISTATS 2025.
Summary updated