Logo image
Back
YOSO: You-Only-Sample-Once via Compressed Sensing for Graph Neural Network Training
Preprint   Open access

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

Yi Li, Zhichun Guo, Guanpeng Li and Bingzhe Li
ArXiV.org
Cornell University
11/08/2024
DOI: 10.48550/arxiv.2411.05693
url
https://doi.org/10.48550/arxiv.2411.05693View
Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

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.
Computer Science - Learning

Details

Metrics

14 Record Views
Logo image