# YOSO: You-Only-Sample-Once via Compressed Sensing for Graph Neural Network Training

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 33 references that are in the map.
- First posted on arXiv 8 Nov 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [A Survey on Spectral Graph Neural Networks](https://mlsanity.com/paper/2302.05631/) (2023)
- [Stochastic Training of Graph Convolutional Networks with Variance Reduction](https://mlsanity.com/paper/1710.10568/) (2017)

## Abstract (arXiv)

Graph neural networks (GNNs) have become essential tools for analyzing non-Euclidean data across various domains. During training stage, sampling plays an important role in reducing latency by limiting the number of nodes processed, particularly in large-scale applications. However, as the demand for better prediction performance grows, existing sampling algorithms become increasingly complex, leading to significant overhead. To mitigate this, we propose YOSO (You-Only-Sample-Once), an algorithm designed to achieve efficient training while preserving prediction accuracy. YOSO introduces a compressed sensing (CS)-based sampling and reconstruction framework, where nodes are sampled once at input layer, followed by a lossless reconstruction at the output layer per epoch. By integrating the reconstruction process with the loss function of specific learning tasks, YOSO not only avoids costly computations in traditional compressed sensing (CS) methods, such as orthonormal basis calculations, but also ensures high-probability accuracy retention which equivalent to full node participation. Experimental results on node classification and link prediction demonstrate the effectiveness and efficiency of YOSO, reducing GNN training by an average of 75% compared to state-of-the-art methods, while maintaining accuracy on par with top-performing baselines.