# Linear-Time Graph Neural Networks for Scalable Recommendations

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 54 references that are in the map.
- First posted on arXiv 21 Feb 2024.

## Builds on (most cited first, 30 of 33)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation](https://mlsanity.com/paper/2002.02126/) (2020)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Neural Collaborative Filtering](https://mlsanity.com/paper/1708.05031/) (2017)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Neural Graph Collaborative Filtering](https://mlsanity.com/paper/1905.08108/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [KGAT: Knowledge Graph Attention Network for Recommendation](https://mlsanity.com/paper/1905.07854/) (2019)
- [Self-supervised Graph Learning for Recommendation](https://mlsanity.com/paper/2010.10783/) (2020)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)
- [Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1911.07323/) (2019)
- [Are Graph Augmentations Necessary? Simple Graph Contrastive Learning for Recommendation](https://mlsanity.com/paper/2112.08679/) (2021)
- [Implicit Deep Learning](https://mlsanity.com/paper/1908.06315/) (2019)
- [Disentangled Graph Collaborative Filtering](https://mlsanity.com/paper/2007.01764/) (2020)
- [Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba](https://mlsanity.com/paper/1803.02349/) (2018)
- [Implicit Graph Neural Networks](https://mlsanity.com/paper/2009.06211/) (2020)
- [Graph Attention Multi-Layer Perceptron](https://mlsanity.com/paper/2206.04355/) (2022)
- [SimpleX: A Simple and Strong Baseline for Collaborative Filtering](https://mlsanity.com/paper/2109.12613/) (2021)
- [Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks](https://mlsanity.com/paper/2006.13866/) (2020)
- [Graph Trend Filtering Networks for Recommendations](https://mlsanity.com/paper/2108.05552/) (2021)
- [NAIS: Neural Attentive Item Similarity Model for Recommendation](https://mlsanity.com/paper/1809.07053/) (2018)
- [Amazon-M2: A Multilingual Multi-locale Shopping Session Dataset for Recommendation and Text Generation](https://mlsanity.com/paper/2307.09688/) (2023)
- [Macro Graph Neural Networks for Online Billion-Scale Recommender Systems](https://mlsanity.com/paper/2401.14939/) (2024)
- [Fast Graph Condensation with Structure-based Neural Tangent Kernel](https://mlsanity.com/paper/2310.11046/) (2023)
- [Deep Social Collaborative Filtering](https://mlsanity.com/paper/1907.06853/) (2019)
- [GraphFM: Improving Large-Scale GNN Training via Feature Momentum](https://mlsanity.com/paper/2206.07161/) (2022)

## Built on by (most cited first, 30 of 31)

- [A Survey on RAG Meeting LLMs: Towards Retrieval-Augmented Large Language Models](https://mlsanity.com/paper/2405.06211/) (2024)
- [A Survey of Mamba](https://mlsanity.com/paper/2408.01129/) (2024)
- [TokenRec: Learning to Tokenize ID for LLM-based Generative Recommendation](https://mlsanity.com/paper/2406.10450/) (2024)
- [Graph Machine Learning in the Era of Large Language Models (LLMs)](https://mlsanity.com/paper/2404.14928/) (2024)
- [Graph Unlearning with Efficient Partial Retraining](https://mlsanity.com/paper/2403.07353/) (2024)
- [Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows](https://mlsanity.com/paper/2503.09069/) (2025)
- [Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform](https://mlsanity.com/paper/2505.11892/) (2025)
- [You Are What You Bought: Generating Customer Personas for E-commerce Applications](https://mlsanity.com/paper/2504.17304/) (2025)
- [Backdoor Graph Condensation](https://mlsanity.com/paper/2407.11025/) (2024)
- [SORSA: Singular Values and Orthonormal Regularized Singular Vectors Adaptation of Large Language Models](https://mlsanity.com/paper/2409.00055/) (2024)
- [Exposing Privacy Risks in Graph Retrieval-Augmented Generation](https://mlsanity.com/paper/2508.17222/) (2025)
- [Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers](https://mlsanity.com/paper/2501.10688/) (2025)
- [Unlearning Inversion Attacks for Graph Neural Networks](https://mlsanity.com/paper/2506.00808/) (2025)
- [Enhancing Molecular Property Predictions by Learning from Bond Modelling and Interactions](https://mlsanity.com/paper/2603.00568/) (2026)
- [MGM: Global Understanding of Audience Overlap Graphs for Predicting the Factuality and the Bias of News Media](https://mlsanity.com/paper/2412.10467/) (2024)
- [Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiency](https://mlsanity.com/paper/2503.14076/) (2025)
- [Ultra Fast Warm Start Solution for Graph Recommendations](https://mlsanity.com/paper/2509.01549/) (2025)
- [Binary Hypothesis Testing for Softmax Models and Leverage Score Models](https://mlsanity.com/paper/2405.06003/) (2024)
- [Enhance GNNs with Reliable Confidence Estimation via Adversarial Calibration Learning](https://mlsanity.com/paper/2503.18235/) (2025)
- [Attack by Unlearning: Unlearning-Induced Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2603.18570/) (2026)
- [Your Graph Recommender is Provably a Single-view Graph Contrastive Learning](https://mlsanity.com/paper/2407.17723/) (2024)
- [H3GNNs: Harmonizing Heterophily and Homophily in GNNs via Joint Structural Node Encoding and Self-Supervised Learning](https://mlsanity.com/paper/2504.11699/) (2025)
- [PBiLoss: Popularity-Aware Regularization to Improve Fairness in Graph-Based Recommender Systems](https://mlsanity.com/paper/2507.19067/) (2025)
- [Lighter-X: An Efficient and Plug-and-play Strategy for Graph-based Recommendation through Decoupled Propagation](https://mlsanity.com/paper/2510.10105/) (2025)
- [E2E-GRec: An End-to-End Joint Training Framework for Graph Neural Networks and Recommender Systems](https://mlsanity.com/paper/2511.20564/) (2025)
- [AdvSynGNN: Structure-Adaptive Graph Neural Nets via Adversarial Synthesis and Self-Corrective Propagation](https://mlsanity.com/paper/2602.17071/) (2026)
- [A Multi-View Media Profiling Suite: Resources, Evaluation, and Analysis](https://mlsanity.com/paper/2605.01336/) (2026)
- [The Confidence Trap: Calibration Attacks for Graph Neural Networks](https://mlsanity.com/paper/2606.08467/) (2026)
- [DrainSinkhorn: Safe Elimination for Batched Entropic Optimal Transport](https://mlsanity.com/paper/2607.24741/) (2026)
- [PersonaMem-v3: Toward Omni-Platform Personal Intelligence for Holistic User Understanding, Recommendation, and Agentic Tasks](https://mlsanity.com/paper/2608.21381/) (2026)

## Abstract (arXiv)

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.