LTGNN: Linear-Time Graph Neural Networks Make Recommendation Systems Truly Scalable

LTGNN (Linear-Time Graph Neural Networks) is an open-source implementation of a paper accepted at the WWW 2024 conference. Through innovative algorithm design, it reduces the time complexity of graph neural networks from superlinear to linear, solving the computational bottleneck of traditional GNNs in large-scale recommendation scenarios and opening up new possibilities for the large-scale deployment of recommendation systems.

Modern recommendation systems face the contradiction between the exponential growth of user-item interaction graph scale and the limited growth rate of computing resources. Traditional GNNs (such as GCN, GraphSAGE, LightGCN) can capture high-order collaborative signals, but their computational complexity is superlinearly related to the graph scale, leading to memory explosion, slow training, and poor real-time performance, making them difficult to apply in production environments with hundreds of millions of users.

Key insight of LTGNN: In recommendation scenarios, there is no need to compute the complete relationships between all node pairs. Through sampling and aggregation strategies, the complexity can be reduced to linear while maintaining expressive power.

Linear-time strategies: Hierarchical neighbor sampling (sampling by importance), approximate message passing (low-rank approximation/random projection to compress dimensions), incremental update (only compute changed nodes).

Maintaining expressive power: Theoretical proof that linear approximation has the same upper bound of expression as exact computation; adaptive sampling (dynamically adjust strategies to retain key information); multi-scale fusion (combining neighbor information of different granularities).

The PyTorch-based open-source implementation has industrial-grade practical features:

• Efficient sparse matrix operations: Use PyTorch sparse tensors and cuSPARSE optimization libraries to process large-scale sparse interaction data;
• Batch processing and negative sampling: Dynamic negative sampling (adaptive hard negative samples), memory mapping (block loading of ultra-large datasets), multi-GPU support (data/model parallelism);
• Ecosystem compatibility: Supports common formats like LibFM, provides a unified interface with LightGCN/NGCF baselines, and is easy to embed into existing recommendation pipelines.

Accuracy: On datasets like MovieLens, Amazon-Book, and Gowalla, Recall@20 and NDCG@20 metrics are comparable to or even better than baselines like LightGCN and UltraGCN;

Efficiency: Training time for graphs with tens of millions of edges is reduced from hours to tens of minutes, peak memory is reduced by an order of magnitude, and it can stably support graphs with hundreds of millions of edges;

Ablation experiments: Hierarchical sampling contributes the main efficiency improvement, adaptive sampling is crucial for maintaining accuracy, and incremental updates have significant advantages in dynamic scenarios.

LTGNN is suitable for the following scenarios:

• Ultra-large-scale recommendation: E-commerce products, video personalization, social content recommendation (tens of millions/hundreds of millions of users/items);
• Real-time recommendation: Online learning (quick response to user feedback), stream processing (continuous interaction data), A/B testing (fast iteration);
• Resource-constrained environments: Mobile recommendation, embedded device services, low-cost cloud deployment.

LTGNN has the following limitations and research directions:

• Graph structure assumptions: Linear complexity depends on assumptions like sparsity and power-law distribution; performance may degrade on dense graphs;
• Cold start problem: Need to combine content information or meta-learning to alleviate cold start for new users/items;
• Heterogeneous graph extension: Currently designed for user-item bipartite graphs, needs to be extended to heterogeneous graphs with multiple node/edge types.

LTGNN is an important step towards the practicalization and scaling of GNNs in recommendation systems, proving that algorithm design can achieve an order-of-magnitude efficiency improvement without sacrificing performance. For recommendation system developers, it is both a usable tool and an algorithm design example, demonstrating the transformation from theoretical insight to engineering practice and the balance between efficiency and performance.