# SWING: Unlocking Implicit Graph Representations for Graph Random Features

arXiv: https://arxiv.org/abs/2602.12703 · HTML: https://mlsanity.com/paper/2602.12703/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 49 references that are in the map.
- First posted on arXiv 13 Feb 2026.

## Builds on (most cited first, 19 of 19)

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Molecular Graph Convolutions: Moving Beyond Fingerprints](https://mlsanity.com/paper/1603.00856/) (2016)
- [Thingi10K: A Dataset of 10,000 3D-Printing Models](https://mlsanity.com/paper/1605.04797/) (2016)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [On the Scalability of GNNs for Molecular Graphs](https://mlsanity.com/paper/2404.11568/) (2024)
- [Efficient and Interpretable Robot Manipulation with Graph Neural Networks](https://mlsanity.com/paper/2102.13177/) (2021)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [Stability of the Lanczos Method for Matrix Function Approximation](https://mlsanity.com/paper/1708.07788/) (2017)
- [Molecule Generation for Drug Design: a Graph Learning Perspective](https://mlsanity.com/paper/2202.09212/) (2022)
- [MolE: a molecular foundation model for drug discovery](https://mlsanity.com/paper/2211.02657/) (2022)
- [General Graph Random Features](https://mlsanity.com/paper/2310.04859/) (2023)
- [Simplex Random Features](https://mlsanity.com/paper/2301.13856/) (2023)
- [Large sample spectral analysis of graph-based multi-manifold clustering](https://mlsanity.com/paper/2107.13610/) (2021)
- [Efficient Graph Field Integrators Meet Point Clouds](https://mlsanity.com/paper/2302.00942/) (2023)
- [Linear Transformer Topological Masking with Graph Random Features](https://mlsanity.com/paper/2410.03462/) (2024)
- [Graph Random Features for Scalable Gaussian Processes](https://mlsanity.com/paper/2509.03691/) (2025)
- [Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs](https://mlsanity.com/paper/2410.10368/) (2024)
- [Computationally-efficient Graph Modeling with Refined Graph Random Features](https://mlsanity.com/paper/2510.07716/) (2025)
- [Graph-enhanced Optimizers for Structure-aware Recommendation Embedding Evolution](https://mlsanity.com/paper/2310.03032/) (2023)

## Abstract (arXiv)

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: ε-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 algorithm 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.