Computationally-efficient Graph Modeling with Refined Graph Random Features
This work addresses computational bottlenecks in graph modeling for researchers and practitioners, though it is incremental as it builds on existing GRFs.
The paper tackles the problem of inefficient and inaccurate graph kernel computations by proposing GRFs++, which improves upon Graph Random Features with a walk-stitching technique and enhanced termination strategies, achieving greater efficiency and accuracy without extra cost.
We propose refined GRFs (GRFs++), a new class of Graph Random Features (GRFs) for efficient and accurate computations involving kernels defined on the nodes of a graph. GRFs++ resolve some of the long-standing limitations of regular GRFs, including difficulty modeling relationships between more distant nodes. They reduce dependence on sampling long graph random walks via a novel walk-stitching technique, concatenating several shorter walks without breaking unbiasedness. By applying these techniques, GRFs++ inherit the approximation quality provided by longer walks but with greater efficiency, trading sequential, inefficient sampling of a long walk for parallel computation of short walks and matrix-matrix multiplication. Furthermore, GRFs++ extend the simplistic GRFs walk termination mechanism (Bernoulli schemes with fixed halting probabilities) to a broader class of strategies, applying general distributions on the walks' lengths. This improves the approximation accuracy of graph kernels, without incurring extra computational cost. We provide empirical evaluations to showcase all our claims and complement our results with theoretical analysis.