Recommenders over-recommend blockbusters. Current fixes subtract some estimate of global popularity from an item's score. That throws away a signal worth keeping: an item that is popular among people who share your tastes is evidence of taste, while an item that is popular everywhere is mostly evidence of exposure. This proposal separates the two. For each user, we look up a nested chain of increasingly tight-knit cohorts of look-alike users. We score items by how much more often that cohort consumes them than the population at large does. When a user's tight cohort is too small to trust, we back off to looser ones.
The cohorts come from graph theory rather than from clustering learned embeddings. We build a graph linking users with discriminatively weighted overlapping histories. We then decompose it into nested "trusses," subgraphs in which every edge sits inside at least $k-2$ triangles. Raising $k$ yields smaller, tighter groups contained in the looser ones, so the groups form a tree. A precomputed tree index returns a user's whole chain of cohorts in time proportional to the cohort sizes. The two-sentence version: popularity inside your cohesive community is taste and should be kept; popularity beyond it is exposure and should be removed; nested graph communities give a principled, fast way to define "your community" at several scales.
Core Claim
Our main hypothesis is that local popularity bias is better estimated inside cohesive graph communities than inside embedding clusters. The closest prior work is DAP from How Graph Convolutions Amplify Popularity Bias for Recommendation?. That paper proves that graph-convolution recommenders give an item gradient influence growing as $d_i^{3/2}$ in its degree $d_i$, which pulls user embeddings toward popular hubs. It then corrects this after training by clustering embeddings with K-means and subtracting each cluster's estimated popularity effect. The weakness is that the K-means clusters are drawn in a space already distorted by the very bias being removed. Adap-τ shows that item embedding norms grow with interaction frequency, so distances in that space partly measure popularity.
Our cohorts are defined before any embedding is learned, from the discrete co-consumption structure. They are nested rather than flat, and each is retrieved from an index rather than re-clustered at inference. The claim is falsifiable at three levels. The first is whether truss communities in real recommendation data fragment into meaningful groups at all. The second is whether community-relative scoring beats both a flat-neighborhood version and a popularity-bucket version of the same score. The third is whether swapping DAP's K-means clusters for truss communities improves DAP itself.
Research Program
Building the graph. The raw user–item graph is a poor substrate for this idea. Nested cores of the bipartite graph, as indexed in Efficient Index for Temporal Core Queries over Bipartite Graphs, tend to be large, connected, degree-sorted shells rather than topical groups. A user's core number is also close to a function of their degree, which would collapse our method into degree bucketing. We therefore construct a user–user graph whose edge weights discount blockbusters.
The weighting follows An automatic weighting scheme for collaborative filtering, where Jin et al. learned item weights by a leave-one-out objective. They found that niche items are far more discriminative than popular ones: over half of MovieRating items were essentially ignorable, and about 2% carried large weight. Their leave-one-out training scales quadratically, so our default edge weight is a cheap inverse-user-frequency overlap. We use learned PCC+-style weights (Pearson correlation with learned item weights) only on the smaller datasets, as a check. We keep an edge when the weighted overlap clears a threshold. This is where popularity bias first enters the pipeline: without discounting, shared blockbusters connect everyone into one hairball.
Building the hierarchy and the index. We run truss decomposition on this graph and organize the connected $k$-truss components into a containment tree. This follows the hierarchical indexing line of work. D-Forest and the ICP-Index reach query time proportional to output size. The truss indexes of Truss-Based Structural Diversity Search and TC-Tree store maximal connected trusses compactly. We reuse this indexing technique and do not claim novelty for it. What these papers never do is attach preference scoring or popularity statistics to tree nodes, and that is our addition.
Each tree node stores the per-item interaction counts of its member set. The counts are kept in sparse form and computed bottom-up, since a parent's counts are the sum of its children's counts plus those of members that appear only at the parent level. A query for user $u$ walks from $u$'s deepest node to the root. It returns the chain $C_L(u) \subset \dots \subset C_1(u)$ together with the counts.
Scoring. Let $p_l(i)$ be the fraction of members of $C_l(u)$, excluding $u$, who interacted with item $i$. Let $p(i)$ be item $i$'s global interaction rate. We blend levels with a back-off estimate:
$$\hat p(i \mid u) = \sum_{l=1}^{L} w_l(u)\, p_l(i), \qquad w_l(u) \propto |C_l(u)|^{\eta}\, k_l^{\rho}.$$
The weight on level $l$ grows with the community's size $|C_l(u)|$, reflecting reliability, and with its cohesion level $k_l$, reflecting specificity. The exponents $\eta$ and $\rho$ are tuned on validation data. The final score is
$$s(u,i) = \log\big(\hat p(i \mid u) + \epsilon\big) - \gamma \log\big(p(i) + \epsilon\big).$$
Here $\gamma \in [0,1]$ interpolates between pure community popularity ($\gamma = 0$) and pure lift over global popularity ($\gamma = 1$), and $\epsilon$ is a small smoothing constant. This makes explicit the open problem that global debiasing suppresses head items users genuinely like. A blockbuster that is over-represented in $u$'s tight cohort keeps a high score; one that is merely everywhere does not.
Plugging into a learned model. The same community statistics can replace DAP's K-means clusters inside LightGCN. Each user's local amplification is then estimated from the embeddings of their truss community rather than their K-means cluster. This gives a like-for-like test of the structural ingredient inside the strongest graph-based debiasing pipeline.
Relation to other bridges. Three existing works connect communities or trees to recommendation, and none tests this question. Community-Aware Social Community Recommendation relies on explicit social ties and memberships. MISS builds retrieval trees over multimodal features. Non-parametric Graph Convolution for Re-ranking convolves over flat local neighborhoods. None derives cohesive-subgraph hierarchies from interactions or asks how popularity behaves across nesting levels.
The look-alike literature motivates the cohort view. Cai et al. show that look-alike cohorts surface interests outside a user's own history. Our contribution is to make those cohorts nested, cohesive, and popularity-aware.
Relation to PAAC. The research file points out that PAAC's alignment module needs tail items to be co-consumed with head items. Community-relative scoring does not need that. A tail item consumed by a few members of a tight cohort gets a large lift regardless of what else those members consumed.
Baselines
The naive reference point is global most-popular ranking. It anchors how much of any overall accuracy number is popularity. Next to it is plain user-kNN with cosine similarity, which is the similarity-based recommender with no debiasing at all.
The strongest existing methods are PAAC, DAP on LightGCN, MACR, and Adap-τ. All four are run from their authors' protocols on identical splits, with the same hyperparameter search budget as our method (we propose 50 validation trials each).
PAAC is the most dangerous competitor for overall accuracy on debiased tests. It combines supervised alignment of tail items to co-interacted head items with popularity-reweighted contrastive loss. On Yelp2018 it reports improving NDCG@20 by 30.2% and Recall@20 by 8.7% over the strongest baseline. It also reduced the popular–unpopular accuracy gap by 87.5% on Yelp2018 and 34.18% on Gowalla (PAAC).
DAP is the most direct competitor on the tail. It reports Gowalla tail-set Recall and NDCG gains of 23.96% and 28.27%, gains above 50% on Yelp2018's tail, and a 1–5% overall increase (DAP).
MACR is the causal alternative: it trains extra popularity and conformity branches, then subtracts the direct popularity effect at test time. It reports average HR@20 gains of 153% on MF and 241% on LightGCN (MACR). Adap-τ reports a 9% average gain over non-normalized models. No absolute Recall@20 or NDCG@20 values for any of these methods were found on Lacuna; only relative gains are reported. We therefore reproduce all baselines ourselves and compare against our reproductions.
Two ablations isolate the key ingredient. The first, flat-kNN lift, uses the identical scoring rule, but $C_l(u)$ is replaced by $u$'s top-$n_l$ weighted-overlap neighbors, with $n_l$ matched to the truss community sizes. This removes transitive cohesion and nesting while keeping everything else. The second, degree-bucket lift, replaces communities with the set of users in $u$'s activity decile. It tests whether "community" is secretly just "similar activity level." A third structural ablation uses bipartite $(\alpha,\beta)$-cores of the raw graph instead of trusses of the weighted projection.
For the plug-in experiment, DAP-truss is compared with DAP-K-means and with DAP-K-means applied to unit-normalized embeddings. Everything else is held fixed: the backbone, training run, and DAP hyperparameter grid.
We will count the approach as a success under three conditions. On tail Recall@20, it must beat the reproduced DAP by a margin exceeding three-seed standard deviation. On uniform-test NDCG@20, it must be within one standard deviation of reproduced PAAC. And it must beat both flat-kNN lift and degree-bucket lift on tail metrics. For the plug-in variant, DAP-truss must beat DAP-K-means on tail metrics with no overall loss.
Why not just…?
Why not just subtract popularity within degree or popularity buckets? This is the most serious threat. Structural coreness is known to track degree closely, so our communities could be an expensive proxy for activity strata. The degree-bucket lift ablation is designed to settle this. We also report, per dataset, the rank correlation between users' truss depth and degree, and the topical purity of communities within a single degree decile. If degree-bucket lift matches the truss version, we would drop the structural claim and report that finding.
Why not just use user-kNN with a lift correction, no hierarchy? Flat neighborhoods are the classical choice. The research file notes their weakness: tail-heavy users have little raw overlap, so their nearest neighbors are noisy. Transitive cohesion, meaning edges supported by many shared triangles, should reject accidental overlaps that kNN keeps. Nesting should supply a principled back-off for users whose tight cohort is tiny. The flat-kNN lift ablation, stratified by user activity, tests exactly this. If the truss version wins only for low-activity users and ties elsewhere, that is still a precise finding about where structure helps.
Why not just run DAP's K-means on normalized embeddings? Adap-τ shows that normalization removes norm inflation, which may undo much of the distortion we attribute to K-means. However, DAP's own analysis locates the bias in the directions users are pulled toward, not only in norms. Normalized K-means is included as a baseline in the plug-in comparison. If it closes the gap to DAP-truss, the structural argument for the plug-in variant fails, though the standalone scorer may still stand.
Why not just reweight by inverse propensity? MACR reports that inverse propensity weighting is hard to tune and unstable. PAAC outperformed inverse propensity scoring on uniform tests across Amazon-book, Yelp2018, and Gowalla. More fundamentally, global propensity removes community-level popularity along with exposure, which is exactly the signal we aim to keep. We include IPS on MF only as a reference point.
Proposed Experiments
We use Gowalla, Yelp2018, Amazon-book, and MovieLens-1M, the shared benchmarks of the debiasing papers above. We evaluate under three protocols: the uniform debiased test set used by MACR and PAAC, DAP's tail test set of the bottom 80% of items (TR@20), and Adap-τ's ten popularity deciles scored by NDCG@20. We also report overall Recall@20 and NDCG@20.
The first decisive check runs before any recommendation experiment. Do the truss components of the weighted user graph fragment into many mid-sized communities, or collapse into one giant component? We report the component-size distribution per level and the depth–degree correlation. A single dominant component on most levels would stop the standalone scorer.
The second check is the γ sweep, decile by decile. The retention hypothesis predicts that the best γ lies strictly inside (0, 1), and that at that γ top-decile NDCG drops much less than under full global lift. A best γ of 1 would mean community popularity carries no taste signal beyond what lift already provides.
The third check is the ablation ladder described under Baselines: truss versus flat-kNN versus degree-bucket versus $(\alpha,\beta)$-core communities. We break results out by user activity to locate where structure helps.
The fourth check is the DAP plug-in comparison on LightGCN.
Finally, we measure cost. We report index build time and size. We compare per-query candidate-generation latency against brute-force kNN, expecting the index to scale with cohort size rather than graph size, as the indexing literature guarantees. We treat the file's warning that dynamic core maintenance is unbounded under edge insertion as a stated limitation, and evaluate only with periodic rebuilds.
References
- How graph convolutions amplify popularity bias for recommendation?
- Adap-τ : Adaptively Modulating Embedding Magnitude for Recommendation
- Efficient Index for Temporal Core Queries over Bipartite Graphs
- An automatic weighting scheme for collaborative filtering
- Efficient Community Search over Large Directed Graph: An Augmented Index-based Approach
- Influential Community Search in Large Networks
- Truss-Based Structural Diversity Search in Large Graphs
- Finding Theme Communities from Database Networks
- Community-Aware Social Community Recommendation.
- MISS: Multi-Modal Tree Indexing and Searching with Lifelong Sequential Behavior for Retrieval Recommendation
- Non-parametric Graph Convolution for Re-ranking in Recommendation Systems
- Recall-Augmented Ranking: Enhancing Click-Through Rate Prediction Accuracy with Cross-Stage Data
- Popularity-Aware Alignment and Contrast for Mitigating Popularity Bias
- Model-Agnostic Counterfactual Reasoning for Eliminating Popularity Bias in Recommender System