  Graph representation learning has been extensively studied in recent years.
Despite its potential in generating continuous embeddings for various networks,
both the effectiveness and efficiency to infer high-quality representations
toward large corpus of nodes are still challenging. Sampling is a critical
point to achieve the performance goals. 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 the negative sampling distribution should be positively but
sub-linearly correlated to their positive sampling distribution. 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 personalized recommendation, on a total of 19
experimental settings. These relatively comprehensive experimental results
demonstrate its robustness and superiorities.
