When a new user arrives on a platform, a recommender has seen only a handful of their clicks, and it has millions of items they never touched. Training treats those untouched items as negatives. Some of them are things the user simply has not found yet. The usual fix for this kind of imbalance is focal loss, which shrinks the training signal from easy examples and concentrates it on hard ones. For a cold user, though, the "hardest" negatives are exactly the items the model thinks the user would like, so focal loss pushes hardest on the examples most likely to be mislabeled. We propose to compute the focal weight from the model's full uncertainty about the user rather than from one point estimate. A Gibbs sampler, which draws plausible values of the user and item vectors one block at a time, gives us that uncertainty. Each unobserved item is then weighted by how hard it is on average across those draws, multiplied by the posterior probability that it is a true negative and not an undiscovered positive.
The opportunity is that the two failure modes cancel in the right place. A point-estimate model trained on three clicks is confidently wrong in arbitrary directions. A Bayesian model trained on three clicks knows it is uncertain. That uncertainty is what should decide whether a high-scoring unobserved item gets amplified as a hard negative or protected as a likely false negative. We make this concrete inside a sampler whose every step stays conjugate, meaning each conditional distribution is a standard Gaussian that can be sampled exactly.
Core Claim
Focal reweighting and false-negative protection should both be functions of the posterior predictive distribution, not of a single score. This matters most when a user or item has very few interactions. Concretely, let $\psi_{uj}=U_u^\top V_j$ be the score of user $u$ for item $j$, and $p_{uj}=\sigma(\psi_{uj})$ the predicted click probability. For an unobserved pair we set the weight
$$w_{uj} = \mathbb{E}_{\text{post}}\!\left[p_{uj}^{\gamma}\right]\cdot \Pr_{\text{post}}\!\left(p_{uj} < \tau\right),$$
where the expectations are over Gibbs samples of $(U_u, V_j)$, $\gamma$ is the focal exponent, and $\tau$ is a threshold above which an unobserved item is treated as a plausible unseen positive. The first factor is the focal term averaged over the posterior. For a negative, $1-p_t=p$, so this is the standard modulating factor. The second factor is the posterior probability that the item is not a hidden positive. Together they give a bell-shaped weight in the score: weak for easy negatives, strongest for moderately hard ones, and weak again for confidently high-scoring ones.
This resembles the hand-designed gradient of Enhanced Bayesian Personalized Ranking for Robust Hard Negative Sampling in Recommender Systems, but the shape here comes from uncertainty. For a cold user whose posterior over $U_u$ is wide, the second factor stays moderate across a wide range of mean scores, so the model neither commits to amplifying nor to discarding. As evidence accumulates, the curve sharpens. The prediction to test is that this adaptivity helps most at 1 to 5 observed interactions and fades to parity with Hard-BPR on warm users.
Research Program
The base model is Bayesian matrix factorization in the style of Bayesian probabilistic matrix factorization using Markov chain Monte Carlo (BPMF). BPMF places Gaussian–Wishart priors over user and item vectors and Gibbs-samples hyperparameters, users, and items in alternating blocks; we reuse this structure. Two changes are needed.
The first change handles cold start. Following Bayesian Matrix Factorization with Side Information and Dirichlet Process Mixtures, which regresses latent factors on side metadata so that a user with no ratings still gets an informed prior, we let user and item prior means depend linearly on content features. That paper works only with explicit star ratings under a squared-error likelihood and has no notion of imbalance or false negatives. We keep its side-information prior and drop the Dirichlet-process clustering, which would add cost without bearing on our question.
The second change handles implicit feedback while keeping conjugacy. We replace the Gaussian likelihood with a weighted Bernoulli likelihood $\sigma(\psi)^{w y}(1-\sigma(\psi))^{w(1-y)}$. This form admits the standard Pólya-Gamma augmentation: given an auxiliary variable drawn with shape $w$, the conditional for $U_u$ is again Gaussian. Every Gibbs block therefore stays exactly sampleable, and per-pair weights simply rescale the precision contributions. Neither BPMF nor the side-information model addresses this conjugacy limitation for weighted classification losses.
The weights depend on the posterior, so updating them inside every sweep would leave the chain without a well-defined target. We instead run the sampler in rounds. Within a round the weights are fixed, so the chain targets a well-defined weighted (generalized-Bayes) posterior. Between rounds, weights are recomputed from the pooled samples of the previous round. This is an iteratively reweighted posterior, analogous to how EM alternates between a fixed objective and its update, and we will report how many rounds are needed for weights to stabilize.
To keep cost bounded we subsample a fixed number of negatives per user per round, drawn in proportion to the previous round's weights. This makes the sampler approximate, and we measure the effect against full-negative runs on the smallest dataset. The $O(D^3)$ inversion per entity noted in the file is manageable at $D\in\{32,64\}$, because cold users contribute few terms and the inversion is shared across their few positives.
The analysis component asks whether the second factor actually identifies false negatives. We create known false negatives by hiding a fraction of each held-out user's true positives inside the unobserved pool and recording the weight each method assigns to them. The calibration literature on focal loss motivates measuring calibration as well. AdaFocal: Calibration-aware Adaptive Focal Loss and Dual Focal Loss for Calibration document that focal weighting distorts predicted probabilities. Posterior averaging may partly undo that distortion, and if it does not, the proposal should say so.
Baselines
The naive reference is logistic matrix factorization trained with plain binary cross-entropy and uniformly sampled negatives, using the same side-information prior mean so that zero-shot cold users are handled. It shares our model class exactly and differs only in being a point estimate with unweighted negatives. Anything we propose must beat it clearly at every cold-start budget.
The strongest existing competitor on the false-negative question is Hard-BPR from Enhanced Bayesian Personalized Ranking for Robust Hard Negative Sampling in Recommender Systems. It replaces BPR's monotone gradient with a bell-shaped one, $g(x)=\frac{1}{1+a}[\sigma(cx+b)+a]$, that down-weights extreme negatives as likely false negatives, and it is shown to estimate one-way partial AUC. It was evaluated only under 10-core filtering, so its cold-start behavior is unknown, which is precisely our regime. We run it on matrix factorization with identical dimension, identical side-information inputs, and the same hard-negative candidate pool. Its $(a,b,c)$ receive the same tuning budget, in validation trials, that we give $(\gamma,\tau)$. The file reports no numbers for it in a form we can transfer; no reported result found on Lacuna for Hard-BPR under cold-start protocols, so we rerun it ourselves. Beating it means a statistically reliable gain in NDCG@20 on users with 1 to 5 interactions, with no significant loss on warm users.
We also include point-estimate focal loss on logistic matrix factorization, which isolates what posterior averaging adds over ordinary focal weighting. Soft BPR from Soft BPR Loss for Dynamic Hard Negative Sampling in Recommender Systems, which flattens the BPR gradient through a temperature, is a second false-negative-aware loss. For cold-start-specific methods we include DropoutNet (DropoutNet: Addressing Cold Start in Recommender Systems), which trains a network to map content into the collaborative space by randomly dropping collaborative embeddings, and MELO (Meta-Learning with Adaptive Weighted Loss for Imbalanced Cold-Start Recommendation), which learns per-interaction loss weights with a recurrent encoder inside meta-learning. MELO is the closest published combination of cold start and imbalance weighting. It reports results on MovieLens 1M, Amazon Grocery, Amazon Sports, and Yelp, but the file gives no figures; no reported result found on Lacuna for MELO's metric values, so it is rerun under our split.
Three ablations isolate the key ingredient. The first drops the false-negative factor and keeps only the posterior-averaged focal term. The second drops the focal term and keeps only the false-negative factor. The third is the unweighted Pólya-Gamma Bayesian factorization with $\gamma=0$ and $\tau=1$, which tests whether Bayesian averaging alone, without any focal reweighting, accounts for the gains.
Why not just…?
Why not just use Hard-BPR, which already down-weights likely false negatives? Its bell curve has a fixed shape set by $(a,b,c)$, applied identically to a user with two clicks and a user with two hundred. For a cold user the score $x$ that Hard-BPR reads is itself highly uncertain, so a fixed curve will mislabel arbitrarily. Hard-BPR is still the real threat: if its gains hold up under cold start, the uncertainty machinery is unnecessary. The interaction-budget sweep settles this directly. Our method should win at low budgets and tie at high ones; if it ties everywhere, the proposal fails.
Why not just get uncertainty from a deep ensemble or Monte Carlo dropout instead of Gibbs sampling? This is a serious alternative, and it may work about as well. We test it head-on by computing the same weight formula from an ensemble of point-estimate logistic factorizations, matched to our sampler in wall-clock time. We expect ensembles to under-represent uncertainty for cold users, because each member's cold vector collapses toward the same regularized prior mean. Gibbs sampling instead draws from the full conditional, whose spread reflects the actual number of observations. If the matched ensemble performs as well on the hidden-positive recovery test and on cold NDCG, we will report that the weighting rule, not the sampler, is the contribution, and recommend the cheaper ensemble.
Why not just use plain Bayesian matrix factorization, since posterior averaging already tempers overconfidence? Averaging predictions does not change which negatives dominate the likelihood. A Bayesian model with unweighted negatives still lets the easy-negative mass swamp a cold user's few positives, which is the imbalance problem focal loss was built for. The $\gamma=0$, $\tau=1$ ablation measures exactly how much the weighting adds on top of the Bayesian model.
Proposed Experiments
Data come from benchmarks named in the file: MovieLens 1M, Amazon Grocery, Amazon Sports, and Yelp from the MELO evaluation, and Gowalla, Taobao, and Tmall from the Hard-BPR evaluation. All are converted to implicit feedback, and side features are taken where available (genre, category, and text-derived item features; demographics for MovieLens). We hold out 20% of users entirely, and separately 20% of items. For each held-out entity we reveal $k\in\{0,1,3,5,10\}$ interactions and evaluate on the rest, with $k=0$ relying only on the side-information prior. Metrics are Recall@20 and NDCG@20 per budget, expected calibration error of predicted click probabilities on held-out pairs, and wall-clock time.
The decisive check is the hidden-positive test. In each cold user's unobserved pool we plant 10% of their true held-out positives, then compare the average weight each method gives these planted items with the weight it gives true negatives of the same mean score. The claim predicts that our weight on planted positives drops below Hard-BPR's at small $k$ while staying comparable on true hard negatives. If it does not, the false-negative factor is not doing its job, whatever the ranking metrics say.
Secondary checks are whether the cold-user gain grows as $k$ shrinks, whether weights stabilize within a few rounds, and how much negative subsampling costs relative to the full-negative sampler on MovieLens 1M. We also report the matched-compute comparison against the ensemble variant, since that result decides whether Gibbs sampling is worth its cost.
References
- Enhanced Bayesian Personalized Ranking for Robust Hard Negative Sampling in Recommender Systems
- Bayesian probabilistic matrix factorization using Markov chain Monte Carlo
- Bayesian Matrix Factorization with Side Information and Dirichlet Process Mixtures
- AdaFocal: Calibration-aware Adaptive Focal Loss
- Dual Focal Loss for Calibration
- Enhancing Recommender Systems: A Strategy to Mitigate False Negative Impact
- DropoutNet: Addressing Cold Start in Recommender Systems
- Meta-Learning with Adaptive Weighted Loss for Imbalanced Cold-Start Recommendation