![[2602.12703] SWING: Unlocking Implicit Graph Representations for Graph Random Features](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.12703] SWING: Unlocking Implicit Graph Representations for Graph Random Features
Summary
The paper presents SWING, a novel algorithm for computations involving Graph Random Features on implicit graphs, enhancing efficiency through continuous space walks and advanced sampling techniques.
Why It Matters
This research is significant as it addresses the computational challenges of working with implicit graph representations, which are increasingly relevant in machine learning. By introducing SWING, the authors provide a method that is not only efficient but also accelerator-friendly, potentially broadening the applicability of graph-based algorithms in various domains.
Key Takeaways
- SWING leverages continuous space walks for graph computations.
- The algorithm uses a Gumbel-softmax sampling mechanism for efficiency.
- It connects implicit graphs with Fourier analysis for improved performance.
- SWING is designed to be accelerator-friendly, avoiding the need for graph materialization.
- The paper includes thorough experimental validation across different implicit graph classes.
Computer Science > Machine Learning arXiv:2602.12703 (cs) [Submitted on 13 Feb 2026] Title:SWING: Unlocking Implicit Graph Representations for Graph Random Features Authors:Alessandro Manenti, Avinava Dubey, Arijit Sehanobish, Cesare Alippi, Krzysztof Choromanski View a PDF of the paper titled SWING: Unlocking Implicit Graph Representations for Graph Random Features, by Alessandro Manenti and 4 other authors View PDF HTML (experimental) Abstract: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 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 pr...