  In an era of information explosion, recommender systems are vital tools to
deliver personalized recommendations for users. The key of recommender systems
is to forecast users' future behaviors based on previous user-item
interactions. Due to their strong expressive power of capturing high-order
connectivities in user-item interaction data, recent years have witnessed a
rising interest in leveraging Graph Neural Networks (GNNs) to boost the
prediction performance of recommender systems. Nonetheless, classic Matrix
Factorization (MF) and Deep Neural Network (DNN) approaches still play an
important role in real-world large-scale recommender systems due to their
scalability advantages. Despite the existence of GNN-acceleration solutions, it
remains an open question whether GNN-based recommender systems can scale as
efficiently as classic MF and DNN methods. In this paper, we propose a
Linear-Time Graph Neural Network (LTGNN) to scale up GNN-based recommender
systems to achieve comparable scalability as classic MF approaches while
maintaining GNNs' powerful expressiveness for superior prediction accuracy.
Extensive experiments and ablation studies are presented to validate the
effectiveness and scalability of the proposed algorithm. Our implementation
based on PyTorch is available.
