🤖 machine learning

Efficient Recommendations via Graph Coarsening and Label Propagation

This paper proposes a flexible two-stage diffusion framework that combines graph coarsening with label propagation to address scalability challenges in large-scale graph-based recommendations, achieving significant improvements in recommendation quality (up to +24% NDCG@5) while balancing computational efficiency and latency.

Original authors: Alessandro Sbandi, Federico Siciliano, Fabrizio Silvestri

Published 2026-07-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Alessandro Sbandi, Federico Siciliano, Fabrizio Silvestri

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to organize a massive, chaotic city where everyone is connected to everyone else. In the world of computers, this city is called a "graph," and the people are "nodes" connected by "edges" (like friendships or phone calls). When companies want to recommend things to people—like a new phone plan or a streaming service—they look at this giant map to see who likes what. But here's the problem: when the city gets too big (with millions of people), trying to look at every single connection at once is like trying to read every book in a library while running a marathon. It takes forever, and the computer often runs out of energy (or memory) before it finishes. This is why scientists are always looking for smarter ways to shrink these maps without losing the important details, so they can still give great recommendations quickly.

This paper introduces a clever two-step strategy to solve that problem, specifically for a huge telecommunications company with over 13 million users. The authors, Alessandro Sbandi, Federico Siciliano, and Fabrizio Silvestri, propose a method that acts like a smart city planner. Instead of trying to understand every single person individually right away, they first group people into "families" or "communities" based on real-world rules, like sharing a last name, calling each other often, or paying each other's bills. They then shrink the giant map down to a smaller version where each "family" is just one big node.

Once the map is smaller, they run a recommendation engine on it. Think of this as asking the "family heads" what the whole family might like. They tested two ways to do this: a fast, simple method called Label Propagation (LPA), which is like passing a note around a circle to see what's popular, and a more complex, brainy method called a Graph Neural Network (GNN), which is like having a super-smart detective figure out patterns. The results were impressive: by using their "family grouping" trick, the simple method improved recommendation quality by 24% compared to trying to analyze the whole giant map at once. When they used the super-smart detective (GNN) on the smaller map, the quality jumped by over 50% compared to the simple method, and it even managed to run where the full map would have crashed the computer.

But the story doesn't end there. The authors realized that just asking the "family head" isn't enough for perfect personalization; you still need to know what you specifically like. So, they added a second step. After getting the general idea from the "family," they zoom back in to each individual person's small circle and refine the suggestions. It's like getting a general suggestion from your parents, and then your best friend tweaking it to make sure it's exactly what you'd want. This two-step process—first shrinking the world to find the big picture, then zooming back in to polish the details—allowed them to make recommendations in less than a second, a speed that is crucial for real-world use.

The paper explicitly argues against simply ignoring the connections or using random shortcuts to shrink the graph, showing that those methods often break the important structures needed for good recommendations. They also found that while the "super-smart detective" (GNN) gives the best results, it requires a lot of training time and computing power, whereas the "note-passing" method (LPA) is incredibly fast and still very effective. The authors are confident in their findings because they tested these ideas on a massive, real-world dataset from January to September 2024, involving millions of users and actual marketing campaigns. They didn't just guess; they measured the results, showing that their approach is not only faster but also significantly better at predicting what users will actually buy, especially when the goal is to pick the top 5 recommendations for a customer.

Technical Summary: Efficient Recommendations via Graph Coarsening and Label Propagation

Problem Statement

Graph-based recommendation systems are widely used in industrial applications, such as telecommunications, to model complex user-item and user-user interactions. However, as these datasets scale to millions or billions of nodes and edges, they face significant challenges in scalability and efficiency. Standard Graph Neural Networks (GNNs), while powerful, often require heavy computational resources, suffer from over-smoothing, and struggle with long-range dependencies in massive graphs. Conversely, lightweight alternatives like the Label Propagation Algorithm (LPA) are computationally efficient but become prohibitively slow when applied directly to full-scale industrial graphs due to the need to iterate over every edge. Furthermore, naive graph downsampling often destroys critical community structures and isolates hubs, degrading recommendation quality. The core challenge is to balance predictive quality with computational cost, specifically in domains where recommendations must be tailored to implicit user groups (e.g., families) rather than just individuals.

Methodology

The authors propose a flexible, two-stage diffusion framework that integrates business-driven graph coarsening with multi-step label propagation. The framework operates on an undirected user graph $G=(V, E, Y)$ and proceeds through three distinct phases:

1. Graph Coarsening (Business-Driven Aggregation)

Instead of using generic community detection algorithms, the method aggregates users into "super nodes" (communities) based on specific domain heuristics relevant to the telecommunications sector. Users are merged if they satisfy conditions such as:

Interaction Frequency: High call duration or frequency.
Surname: Shared family names.
Caring: One user frequently contacting support for another.
Balance: Financial dependencies (e.g., topping up another's balance).
Redundancy: Multiple lines associated with a single user.

This process creates a coarsened graph $G'$ where super nodes represent implicit families or households. A new label matrix $Y'$ is constructed by aggregating the offers accepted by all users within a community.

2. Inter-Community Propagation

A first propagation step is performed on the coarsened graph $G'$ to generate coarse-grained predictions. The framework supports two algorithms for this stage:

Label Propagation Algorithm (LPA): Iteratively updates super node labels based on neighborhood dominance.
Graph Neural Network (GNN): Specifically, a GraphSAGE architecture is applied to a heterogeneous graph representation containing "Community" nodes and "Item" nodes. This models interactions at the community level to predict community-item edges.

3. Intra-Community Propagation

To restore fine-grained personalization, a second propagation step is executed in parallel within each original user-level subgraph.

A representative node $r_c$ is created for each community, containing the aggregated label information from the inter-community step.
This node is connected to all individual users in the community, forming an augmented subgraph $G_{c, aug}$ .
LPA is applied to each subgraph to refine the coarse predictions into individual user recommendations.

Key Contributions

The paper formalizes and validates the following contributions:

Business-Driven Coarsening: A technique that utilizes specific business rules to uncover implicit family structures, preserving essential relationships while reducing graph size by over 70%.
Two-Step Propagation Scheme: An efficient architecture combining coarse-graph diffusion (for scalability) with fine-grained refinement (for accuracy), ensuring low latency and high precision.
Empirical Validation: A comprehensive evaluation against full-graph LPA and alternative coarsening methods (Louvain, Unique label-based), demonstrating significant improvements in scalability and recommendation quality.

Experimental Results

The framework was evaluated on a real-world telecommunications dataset from TIM (Italy) containing over 13 million users and 561 unique promotional offers.

Effectiveness (RQ1):
- Using LPA in both stages, the proposed method achieved a 24% improvement in NDCG@5 over the full-graph LPA baseline.
- Incorporating a lightweight GNN in the first stage further boosted NDCG@5 by more than 50% compared to the LPA-only version and 35% over a GNN trained on a Louvain-coarsened graph.
- The full-graph GNN baseline resulted in an Out-of-Memory (OOM) error, highlighting the necessity of coarsening for GNNs at this scale.
Structural Integrity (RQ2):
- The business-driven coarsening preserved topological properties (degree distribution, clustering coefficients) better than the "Unique" strategy (which created overly tight communities) and offered a better balance than the Louvain method regarding edge density and sparsity.
Efficiency and Scalability (RQ3):
- The coarsening step took only 34 seconds due to pre-computable heuristics.
- The full-graph LPA baseline took over 17 minutes, whereas the proposed method completed the two-stage LPA process in 9 minutes.
- The GNN-enhanced approach took approximately 13 minutes for propagation but remained feasible, whereas the full-graph GNN was infeasible.
- The second (intra-community) propagation step is highly parallelizable and operates on small subgraphs, enabling sub-second inference times for individual user recommendations.
Ablation (RQ4):
- Performance improved with an increasing number of propagation layers ( $L$ ), peaking at $L=5$ with a damping factor $\alpha=0.5$ . Unlike other methods, the proposed framework showed clear sensitivity to these hyperparameters, indicating that deeper propagation within the coarsened structure yields significant gains.

Significance and Claims

The paper claims that graph coarsening is indispensable for applying GNNs to large-scale industrial graphs, as it prevents memory failures and reduces computational overhead. The proposed framework demonstrates that a business-driven approach to coarsening is superior to generic algorithms (like Louvain) for recommendation tasks involving implicit social structures (e.g., families).

The authors emphasize that their approach delivers an optimal balance between scalability, latency, and recommendation quality. Specifically:

The LPA-only pipeline is immediately deployable in low-latency production environments.
The GNN-enhanced option is suitable for settings where higher predictive performance justifies the additional training cost.
The method is particularly effective for family-oriented offers, where recommending the same item to multiple members of a household is redundant; the coarsening step naturally addresses this by aggregating user intent at the community level before refining it.

The work concludes that this coarsening-driven approach is practically applicable to real-world marketing campaigns where maintaining high-quality recommendations while managing frequent changes in user interactions is critical.