Recommenders trained on implicit feedback (clicks, purchases) see only the items each user did interact with. To learn, they must also pick "negatives": items the user supposedly does not want. In catalogs where more than 99.9% of user-item pairs are empty, two things make this hard. Items drawn at random are almost always trivially irrelevant, so they teach the model little. Items the model already scores highly are often things the user would like but never saw, so treating them as negatives teaches the model the wrong lesson. We propose to draw negatives from a small Markov chain kept for each user. At each step the chain proposes a new item by walking two steps on the interaction graph (item, to a user who liked it, to another item that user liked). A Metropolis-Hastings accept/reject test then decides whether to move. That test is the standard MCMC rule that corrects a biased proposal so the chain ends up sampling from any target distribution we choose, without ever normalizing over the full catalog.
The central observation makes this cheap. The two-step walk on a bipartite graph is reversible with respect to item degree, so the correction term for its popularity bias collapses to a ratio of two item degrees. The graph therefore supplies proposals that land in the user's relevant region of a huge, long-tailed catalog, where uniform candidates rarely go. The accept/reject step removes the walk's pull toward popular items. The target itself is a "boundary band": it favors hard items but suppresses those scoring at or above the user's own positives, which are the likely false negatives. The state cost is one integer per user.
Core Claim
For each user $u$ with current scores $s_{uj}$ (the dot product of user and item embeddings), we sample negatives from
$$\pi_u(j) \propto \exp(s_{uj}/\tau)\,\big[1-\sigma\big((s_{uj}-m_u)/\delta\big)\big],$$
where $\tau$ is a temperature and $\sigma$ is the logistic function. The quantity $m_u$ is a running average of the user's scores on their observed positives, and $\delta$ sets how sharply items scoring above that level are down-weighted. We sample from this distribution with a chain whose state is one item index.
With probability $\alpha$, the chain takes a graph-walk move from item $i$ to item $j$. Because the two-step walk satisfies $\deg(i)\,q(j\mid i)=\deg(j)\,q(i\mid j)$, the Metropolis-Hastings acceptance probability reduces to
$$A(i\to j)=\min\Big(1,\ \frac{\pi_u(j)\,\deg(i)}{\pi_u(i)\,\deg(j)}\Big).$$
This needs only two scores and two degrees. Otherwise the chain takes a uniform independence move over all items, which keeps it able to reach any item, including isolated long-tail ones. Each move type preserves $\pi_u$ on its own, so any random mixture of them does too.
We claim three things. On sparse benchmarks, this sampler raises top-$N$ accuracy and long-tail accuracy over uniform, dynamic hard, and in-batch negatives. It does so while sampling fewer eventual test positives as negatives. And both the degree correction and the band factor matter: neither raw graph-walk negatives nor a plain softmax target reaches the same result.
Relation to Prior Work
The closest work is EMC2. It keeps one Metropolis-Hastings state per training point to sample from the full-dataset softmax used by contrastive losses, which cancels the partition function. It proves $O(1/\sqrt{T})$ convergence independent of batch size, and it reports being roughly 2x faster than SimCLR and SogCLR, and 3x faster than negative caching, to reach a target accuracy on STL-10 at batch size 32. We reuse its core mechanism: persistent chains updated online as the encoder changes. We differ in three ways that only arise in recommendation. EMC² works on images with generic proposals, whereas we use graph-structured proposals with an exact, cheap degree correction. EMC² targets the monotone softmax, which on implicit feedback puts the most mass on false negatives, whereas our target is a band. And we run under the joint Bayesian Personalized Ranking (BPR) plus contrastive losses of modern graph recommenders rather than pure instance discrimination.
The motivation comes from Negative Sampling in Recommendation: A Survey and Future Directions. It names the false-negative problem and the trade-off between accuracy, efficiency, and stability as open. It calls for negative sampling that is principled rather than heuristic and that avoids full-catalog normalizers.
ADAR supplies the intuition that useful negatives sit near a decision-boundary transition point rather than at the top of the score list. ADAR, however, synthesizes continuous virtual embeddings by diffusion. We sample real catalog items from a distribution designed around that boundary, so every negative is an actual item whose hardness can be inspected.
Two works constrain the design. SimGCL shows that the benefit of contrastive learning in recommendation comes mostly from pushing embeddings toward uniformity on the hypersphere, not from structural graph augmentation. It improves Recall@20 on Amazon-Book by over 25% relative to LightGCN. We therefore build on SimGCL rather than replace it, and we must check that concentrated negatives do not undo that uniformity. LightGCN fixes the backbone. It removes feature transforms and nonlinearities and aggregates neighbors linearly, which makes it the natural encoder for all methods compared here.
The Bayesian lines are out of scope because they address a different question. Mult-VAE and BGCL quantify uncertainty over representations. We use MCMC to sample negatives, not to infer embedding posteriors.
Research Program
We will build the sampler as a drop-in replacement for the negative-sampling step of LightGCN trained with BPR. We will also plug it into SimGCL, where it supplies the negatives for the BPR term while the contrastive term stays unchanged.
Each user keeps one chain state. We take $K$ chain steps per user per minibatch, with $K$ between 1 and 5. Proposals use the training graph only, and degrees are precomputed. To gain throughput we will test attaching chains to user-positive pairs rather than users, and report memory in both cases.
The analysis has three parts. First, we will derive how the band parameter $\delta$ trades hardness against false-negative rate. Second, we will measure empirically how the mixing weight $\alpha$ governs coverage of long-tail items. Third, we will ask whether the stationary negative distribution raises or lowers the hyperspherical uniformity that SimGCL identifies as the source of its gains. We will measure uniformity with the standard log-mean-exponential pairwise-distance statistic on normalized item embeddings.
Baselines
The naive reference point is LightGCN trained with BPR and uniform negatives, the static uniform sampling the survey describes. It costs one random draw per negative and is the floor every method must clear.
The strongest existing method is SimGCL with its published settings: uniform noise magnitude $\epsilon$, contrastive weight, and temperature. The file reports its gain only in relative terms, over 25% Recall@20 improvement over LightGCN on Amazon-Book, alongside a 17.4% relative gain for SGL-ED from SGL. No absolute Recall@20 or NDCG@20 values were found on Lacuna for any of these datasets, so we will reproduce all baselines ourselves in one codebase. SimGCL is the relevant bar because it is the simplest method known to fix popularity bias under sparsity. Beating it means that SimGCL with our sampler improves Recall@20 and NDCG@20 over SimGCL with uniform negatives, beyond seed variance, on at least three of four datasets, and improves long-tail recall on Amazon-Book.
Dynamic hard negative sampling (DNS) is the most direct competitor on the negative-sampling question. It draws $M$ uniform candidates and keeps the highest-scoring one. We will give it the same budget of score evaluations per negative as our chain, $M=2K$. We will also run a filtered variant of DNS that discards candidates scoring above $m_u$. This variant applies our band idea without any chain, so it isolates whether persistence and graph proposals add anything beyond the target.
An EMC2-style port uses a softmax target and uniform proposals. It isolates our two changes relative to the closest prior work.
ADAR used as a plug-in adds synthesized negatives. No reported result was found on Lacuna for ADAR on Yelp2018, Amazon-Book, Gowalla, or iFashion.
The ablations remove one ingredient each. The first drops the degree correction, so it samples raw two-hop items. The second drops the band factor. The third re-initializes the chain every step. The fourth uses sampling-importance-resampling from $2K$ graph-walk candidates in place of the chain.
For fairness, all methods use the same LightGCN backbone and embedding size. Each gets an identical 30-trial search on validation NDCG@20 over its own hyperparameters, and the same epoch cap with early stopping. Wall-clock time is measured on the same hardware.
Why not just…?
Why not just use DNS with a score filter? This is the real threat. If filtered DNS matches our sampler at equal score evaluations, then the band target alone is the contribution and the chain machinery is not worth its complexity. We would report exactly that. Our expectation is otherwise. In Amazon-Book's long-tailed catalog, $2K$ uniform candidates rarely include items in the user's neighborhood, whereas the graph walk reaches them in one move. The matched-budget comparison, broken down by catalog size and user activity, settles this.
Why not just sample two-hop graph neighbors as negatives? Raw graph walks visit items in proportion to degree, so they over-sample popular items. That feeds exactly the popularity bias that SimGCL shows harms sparse recommenders. The ablation without degree correction measures this directly through the popularity distribution of sampled negatives and through long-tail recall.
Why not just rely on SimGCL, since uniformity already fixes sparsity? SimGCL regularizes the embedding geometry but leaves its BPR negatives uniform, so the ranking loss still sees mostly easy items. The two mechanisms are complementary unless concentrated negatives damage uniformity. We will measure uniformity alongside accuracy. If our sampler lowers uniformity and loses long-tail recall, the claim fails.
Why not just synthesize negatives, as ADAR does? Synthesis avoids false negatives by construction but produces embeddings that correspond to no real item. It was evaluated on different datasets, largely with sequential recommenders. We run it as a baseline on the same backbone. A tie would favor our method only on interpretability and cost, and we would say so.
Proposed Experiments and Decisive Checks
We will use Yelp2018, Amazon-Book, Gowalla, and Alibaba-iFashion with the standard splits used by LightGCN and SGL. We report Recall@20 and NDCG@20 overall, recall on the 80% least popular items, wall-clock time to peak validation NDCG, and memory.
The decisive diagnostic is a false-negative rate. At fixed training checkpoints, we compute the fraction of sampled negatives that appear among the user's held-out test positives. We then plot this rate against hardness, measured as the mean score margin of sampled negatives below $m_u$, for every sampler. Our sampler should sit at a better point on this curve: equally hard, with fewer false negatives. The softmax-target port should show the highest false-negative rate. A second diagnostic tracks chain acceptance rate and the fraction of the catalog visited, as a function of $\alpha$, to show that the uniform move keeps long-tail items reachable.
The proposal fails if the sampling-importance-resampling or filtered-DNS ablations match the full method, or if SimGCL with our sampler does not beat SimGCL with uniform negatives. Either outcome would locate the value, if any, in the target rather than in MCMC.
References
- EMC2: Efficient MCMC Negative Sampling for Contrastive Learning with Global Convergence
- Negative Sampling in Recommendation: A Survey and Future Directions
- Adaptive Diffusion-based Augmentation for Recommendation
- Are Graph Augmentations Necessary?: Simple Graph Contrastive Learning for Recommendation
- LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation
- Variational Autoencoders for Collaborative Filtering
- Bayesian Graph Contrastive Learning
- Self-supervised Graph Learning for Recommendation