Understanding Negative Sampling in Graph Representation Learning

Citations Over TimeTop 10% of 2020 papers

Abstract

Graph representation learning has been extensively studied in recent years, in which sampling is a critical point. Prior arts usually focus on sampling positive node pairs, while the strategy for negative sampling is left insufficiently explored. To bridge the gap, we systematically analyze the role of negative sampling from the perspectives of both objective and risk, theoretically demonstrating that negative sampling is as important as positive sampling in determining the optimization objective and the resulted variance. To the best of our knowledge, we are the first to derive the theory and quantify that a nice negative sampling distribution is pn(u|v) ∝ pd(u|v)α, 0 < α < 1. With the guidance of the theory, we propose MCNS, approximating the positive distribution with self-contrast approximation and accelerating negative sampling by Metropolis-Hastings. We evaluate our method on 5 datasets that cover extensive downstream graph learning tasks, including link prediction, node classification and recommendation, on a total of 19 experimental settings. These relatively comprehensive experimental results demonstrate its robustness and superiorities.

Related Papers

• → Environmental and mental conditions predicting the experience of involuntary musical imagery: An experience sampling method study(2015)47 cited
• → Increased Frustration Predicts the Experience of Time Slowing-Down: Evidence from an Experience Sampling Study(2018)22 cited
• → The Qwantify app dataset: A remote experience sampling study of desire, emotion, and well-being(2022)1 cited
• → Researching robustness of information system for measuring of microcontrollers average power consumption(2017)
• → The Qwantify app dataset: A remote experience sampling study of desire, emotion, and well-being(2022)