# Efficient Recommendations via Graph Coarsening and Label Propagation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 45 references that are in the map.
- First posted on arXiv 24 Jul 2026.

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

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)
- [A Survey of Graph Neural Networks for Recommender Systems: Challenges, Methods, and Directions](https://mlsanity.com/paper/2109.12843/) (2021)
- [Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba](https://mlsanity.com/paper/1803.02349/) (2018)
- [Scaling Up Graph Neural Networks Via Graph Coarsening](https://mlsanity.com/paper/2106.05150/) (2021)
- [A Review on Graph Neural Network Methods in Financial Applications](https://mlsanity.com/paper/2111.15367/) (2021)
- [A Survey of Graph Neural Networks for Social Recommender Systems](https://mlsanity.com/paper/2212.04481/) (2022)
- [Spectrally approximating large graphs with smaller graphs](https://mlsanity.com/paper/1802.07510/) (2018)
- [Graph Coarsening with Neural Networks](https://mlsanity.com/paper/2102.01350/) (2021)
- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [Product Knowledge Graph Embedding for E-commerce](https://mlsanity.com/paper/1911.12481/) (2019)
- [LiGNN: Graph Neural Networks at LinkedIn](https://mlsanity.com/paper/2402.11139/) (2024)
- [Understanding GNN Computational Graph: A Coordinated Computation, IO, and Memory Perspective](https://mlsanity.com/paper/2110.09524/) (2021)
- [Global Neighbor Sampling for Mixed CPU-GPU Training on Giant Graphs](https://mlsanity.com/paper/2106.06150/) (2021)
- [Heterogeneous Global Graph Neural Networks for Personalized Session-based Recommendation](https://mlsanity.com/paper/2107.03813/) (2021)
- [M2GRL: A Multi-task Multi-view Graph Representation Learning Framework for Web-scale Recommender Systems](https://mlsanity.com/paper/2005.10110/) (2020)
- [TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs](https://mlsanity.com/paper/2308.03578/) (2023)
- [Large network community detection by fast label propagation](https://mlsanity.com/paper/2209.13338/) (2022)

## Abstract (arXiv)

Graph-based recommendations are widely adopted in real-world industrial applications. However, graphs in these systems often reach a massive scale, posing notable scalability and efficiency challenges. This requires techniques that can effectively balance predictive quality with computational cost. One promising approach is graph coarsening, an adaptive graph reduction technique that offers a way to systematically construct smaller, yet structurally representative, versions of the original large-scale graphs. In this work, we propose a flexible two-stage diffusion framework that combines graph coarsening with multi-step label propagation in the telecommunications domain. Domain-specific heuristics are applied to first aggregate nodes into meaningful communities, reducing graph size while preserving essential business-relevant relationships. An initial diffusion process done by a Label Propagation Algorithm (LPA) or a Graph Neural Network (GNN) propagates labels across the coarsened graph to produce coarse-grained predictions. Finally, a second LPA within subgraphs generates the final recommendations for individual users. On a real-world telecommunications dataset, when using LPA in both stages, our method achieves up to +24% NDCG@5 over the full-graph LPA baseline. Incorporating a lightweight GNN in the first stage further boosts NDCG@5 by more than 50%, but requires substantial training and inference time. Through extensive experiments and a detailed ablation, we quantify these trade-offs and demonstrate that our coarsening-driven approach delivers an optimal balance between scalability, latency, and recommendation quality.