Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs
This work addresses the computational bottleneck for graph kernel methods in machine learning, enabling efficient implicit graph kernel learning on massive datasets that were previously infeasible.
The authors tackled the problem of computing general random walk graph kernels (RWKs) on sparse graphs, achieving the first linear time complexity randomized algorithms for unbiased approximation, which are up to 27 times faster than previous methods and scale to graphs 128 times larger than brute-force approaches.
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 $\mathbb{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{27\times}$ faster than its counterparts for efficient computation on large graphs and scales to graphs $\mathbf{128 \times}$ bigger than largest examples amenable to brute-force computation.