SWING: Unlocking Implicit Graph Representations for Graph Random Features

We propose SWING: Space Walks for Implicit Network Graphs, a new class of algorithms for computations involving Graph Random Features on graphs given by implicit representations (i-graphs), where edge-weights are defined as bi-variate functions of feature vectors in the corresponding nodes. Those classes of graphs include several prominent examples, such as: *$\epsilon$-neighborhood* graphs, used on regular basis in machine learning. Rather than conducting walks on graphs' nodes, those methods rely on walks in continuous spaces, in which those graphs are embedded. To accurately and efficiently approximate original combinatorial calculations, SWING applies customized Gumbel-softmax sampling mechanism with linearized kernels, obtained via random features coupled with importance sampling techniques. This mechanism is of its own interest. SWING relies on the deep connection between implicitly defined graphs and Fourier analysis, presented in this paper. SWING is accelerator-friendly and does not require input graph materialization. We provide detailed analysis of SWING and complement it with thorough experiments on different classes of i-graphs.

Graph kernels are a powerful way to use relational information in machine learning, but applying them can be computationally expensive. Existing approximations, such as Graph Random Features (GRF), can provide large speedups, but they still require explicitly building the graph, which becomes a bottleneck at scale. We propose SWING, a new method that combines Gumbel-softmax sampling with kernel linearization to avoid graph materialization altogether for implicitly defined graphs. This allows graph-kernel computations to scale linearly with the number of nodes. Furthermore, it is natively accelerator-friendly and seamlessly adapts to hardware like GPUs and TPUs. Empirically, we observe that SWING produces speedups exceeding one order of magnitude while matching the approximation accuracy of GRFs.