Negative Sampling From the Ground Up: A Redesign for Recommendation

Negative sampling is an important yet challenging component in self-supervised graph representation learning, particularly for recommendation systems where user-item interactions are modeled as bipartite graphs. Existing methods often rely on heuristics or human-specified principles to design negative sampling distributions. This potentially overlooks the usage of an underlying ``true'' negative distribution, which we might be able to access as an oracle despite not knowing its exact form. In this work, we shift the focus from manually designing negative sampling distributions to a more principled method that approximates and leverages the underlying true distribution from the ground up. We expand this idea in the analysis of two scenarios: (1) when the observed graph is an unbiased sample from the true distribution, and (2) when the observed graph is biased with partially observable positive edges. The analysis result is the derivation of a sampling strategy as the numerical approximation of a well-established learning objective. Our theoretical findings are also empirically validated, and our new sampling methods achieve state-of-the-art performance on real-world datasets.

Recommender systems suggest content by learning from our past interactions. To learn effectively, these systems must also understand what we dislike, a process called "negative sampling". In fact, "negative sampling" is so important because it generates more than half of the data used to train recommender systems. However, negative sampling is highly suboptimal in the recommender systems nowadays, where developers rely on human-specified heuristics to generate these negative examples. However, this ignores the true, real-world distribution of what users actually dislike—especially since platforms usually only record what we do click on, creating a biased view of our preferences. In this paper, instead of relying on human guesses, we built a method to approximate and use this true, underlying distribution of negative examples from the ground up. We developed a way to use the structural connections in the data to automatically correct for observation biases while the system trains. When applied to real-world recommendation data, our sampling strategy achieved state-of-the-art performance, outperforming existing models. By rooting the learning process in an objective optimization goal rather than human design, our research offers a more accurate foundation for building recommendation systems.