Computationally-efficient Graph Modeling with Refined Graph Random Features

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 approximation accuracy of graph kernels, without incurring extra computational cost. We provide empirical evaluations to showcase our claims and complement our results with theoretical analysis.

Many real world systems like social networks, biological pathways, recommendation engines can be naturally represented as graphs where various entities are nodes that are connected by edges. To analyze these graphs, researchers use "graph kernels", which are mathematical functions that measure the similarity or the relationship between two nodes based on their connections. Computing these similarity scores is extremely expensive for large graphs, with time growing cubically with the number of nodes. Previous works introduce a technique called Graph Random Features (GRF) that approximate these similarity scores cheaply by sending random walkers on the graph and record what they encounter (like the nodes and the weights of the edges). To meaningfully capture relationships between distant nodes, these random walks need to be long which incur a higher cost. Moreover a random walk is inherently sequential and cannot be made parallel. We introduce GRF++, which solves this by "glue-ing" several short walks together rather than sampling a long walk. This is like ensembling a long road trip from independently planned short segments, which is easier to organize, easy to parallelize and still gives the accurate picture of the entire route. Our method enables faster and more accurate estimation of these graph kernels and allows for improvements in various downstream applications.