Linear-Time Graph Neural Networks for Scalable Recommendations This paper proposes a Linear-Time Graph Neural Network (LTGNN) to enable scalable recommendation systems that leverage Graph Neural Networks (GNNs) while maintaining the scalability of traditional methods like Matrix Factorization (MF) and Deep Neural Networks (DNN). The key challenge is to achieve linear computational complexity while preserving the expressive power of GNNs for accurate predictions. LTGNN uses an implicit graph modeling approach with a single propagation layer and an efficient variance-reduced neighbor sampling strategy to reduce computational costs and approximation errors. The model is designed to handle large-scale user-item interaction graphs efficiently, achieving linear time complexity with respect to the number of edges. Extensive experiments on three real-world datasets demonstrate that LTGNN outperforms existing GNN-based and traditional recommendation models in terms of both prediction accuracy and computational efficiency. The proposed method significantly reduces training time while maintaining comparable recommendation performance. The implementation is available on GitHub.Linear-Time Graph Neural Networks for Scalable Recommendations This paper proposes a Linear-Time Graph Neural Network (LTGNN) to enable scalable recommendation systems that leverage Graph Neural Networks (GNNs) while maintaining the scalability of traditional methods like Matrix Factorization (MF) and Deep Neural Networks (DNN). The key challenge is to achieve linear computational complexity while preserving the expressive power of GNNs for accurate predictions. LTGNN uses an implicit graph modeling approach with a single propagation layer and an efficient variance-reduced neighbor sampling strategy to reduce computational costs and approximation errors. The model is designed to handle large-scale user-item interaction graphs efficiently, achieving linear time complexity with respect to the number of edges. Extensive experiments on three real-world datasets demonstrate that LTGNN outperforms existing GNN-based and traditional recommendation models in terms of both prediction accuracy and computational efficiency. The proposed method significantly reduces training time while maintaining comparable recommendation performance. The implementation is available on GitHub.