Efficient Recommendations via Graph Coarsening and Label Propagation
Abstract Overview
This paper studies large-scale graph-based recommendation in telecommunications, where full-graph propagation is computationally expensive and Graph Neural Networks (GNNs) can run out of memory. The authors propose a two-stage diffusion framework that first coarsens the user graph into business-meaningful communities using heuristics such as interaction frequency, shared surnames, and financial dependencies. An initial propagation step is then performed on the coarsened graph using either label propagation (LPA) or a lightweight GraphSAGE model, followed by a second LPA step to refine predictions within each community. Experiments on a real 13.8 million-user dataset compare the method against full-graph approaches and alternative coarsening strategies.
Novelty
The main contribution is the integration of domain-driven graph coarsening with a two-stage diffusion pipeline that separates inter-community recommendation from intra-community personalization. Unlike generic coarsening baselines such as Louvain, the method uses business rules to form subgraphs that reflect implicit family or household structures in an industrial setting.
Results
With LPA in both stages, the proposed method achieves the best LPA-based performance and improves NDCG@5 by 24% over the full-graph LPA baseline (0.0341 vs. 0.0275). Using a GNN in the first stage further raises NDCG@5 to 0.0524, successfully bypassing the out-of-memory errors encountered when training the GNN on the original full graph. Efficiency-wise, the proposed coarsening takes approximately 34 seconds, and the intra-community refinement step averages 358 milliseconds per community, enabling rapid online inference.
Key Points
- The framework coarsens a 13.8 million-node user graph into business-informed communities before applying inter-community propagation and intra-community refinement.
- Compared to full-graph label propagation and alternative coarsening methods, the proposed approach yields the strongest recommendation quality among LPA variants and the highest overall accuracy when paired with a first-stage GNN.
- The paper explicitly quantifies the trade-offs between accuracy, structural fidelity, and scalability, demonstrating that the LPA-only variant provides a lower-latency option while GNN incorporation maximizes predictive performance.