YOSO: You-Only-Sample-Once via Compressed Sensing for Graph Neural Network Training
This addresses the problem of high latency in large-scale GNN training for domains like social networks or bioinformatics, offering a significant efficiency improvement.
The paper tackles the computational overhead of sampling in graph neural network training by proposing YOSO, a compressed sensing-based method that samples nodes once and reconstructs them losslessly, reducing training time by an average of 75% while maintaining accuracy comparable to state-of-the-art baselines.
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.