Understanding Negative Sampling in Graph Representation Learning

• URL: http://arxiv.org/abs/2005.09863v2
• Date: Thu, 25 Jun 2020 04:10:30 GMT
• Title: Understanding Negative Sampling in Graph Representation Learning
• Authors: Zhen Yang, Ming Ding, Chang Zhou, Hongxia Yang, Jingren Zhou and Jie Tang
• Abstract summary: We show that negative sampling is as important as positive sampling in determining the optimization objective and the resulted variance. We propose Metropolis-Hastings (MCNS) to approximate the positive distribution with self-contrast approximation and accelerate 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.
• Score: 87.35038268508414
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Diffusion-based Negative Sampling on Graphs for Link Prediction [8.691564173331924]
  Link prediction is a fundamental task for graph analysis with important applications on the Web, such as social network analysis and recommendation systems. We propose a novel strategy of multi-level negative sampling that enables negative node generation with flexible and controllable hardness'' levels from the latent space. Our method, called Conditional Diffusion-based Multi-level Negative Sampling (DMNS), leverages the Markov chain property of diffusion models to generate negative nodes in multiple levels of variable hardness.
  arXiv  Detail & Related papers  (2024-03-25T23:07:31Z)
• Contrastive Learning with Negative Sampling Correction [52.990001829393506]
  We propose a novel contrastive learning method named Positive-Unlabeled Contrastive Learning (PUCL) PUCL treats the generated negative samples as unlabeled samples and uses information from positive samples to correct bias in contrastive loss. PUCL can be applied to general contrastive learning problems and outperforms state-of-the-art methods on various image and graph classification tasks.
  arXiv  Detail & Related papers  (2024-01-13T11:18:18Z)
• Rethinking Collaborative Metric Learning: Toward an Efficient Alternative without Negative Sampling [156.7248383178991]
  Collaborative Metric Learning (CML) paradigm has aroused wide interest in the area of recommendation systems (RS) We find that negative sampling would lead to a biased estimation of the generalization error. Motivated by this, we propose an efficient alternative without negative sampling for CML named textitSampling-Free Collaborative Metric Learning (SFCML)
  arXiv  Detail & Related papers  (2022-06-23T08:50:22Z)
• Negative Sampling for Recommendation [7.758275614033198]
  How to effectively sample high-quality negative instances is important for well training a recommendation model. We argue that a high-quality negative should be both textitinformativeness and textitunbiasedness
  arXiv  Detail & Related papers  (2022-04-02T09:50:19Z)
• Language Model-driven Negative Sampling [8.299192665823542]
  Knowledge Graph Embeddings (KGEs) encode the entities and relations of a knowledge graph (KG) into a vector space with a purpose of representation learning and reasoning for an ultimate downstream task (i.e., link prediction, question answering) Since KGEs follow closed-world assumption and assume all the present facts in KGs to be positive (correct), they also require negative samples as a counterpart for learning process for truthfulness test of existing triples. We propose an approach for generating negative sampling considering the existing rich textual knowledge in KGs.
  arXiv  Detail & Related papers  (2022-03-09T13:27:47Z)
• Hard Negative Sampling via Regularized Optimal Transport for Contrastive Representation Learning [13.474603286270836]
  We study the problem of designing hard negative sampling distributions for unsupervised contrastive representation learning. We propose and analyze a novel min-max framework that seeks a representation which minimizes the maximum (worst-case) generalized contrastive learning loss.
  arXiv  Detail & Related papers  (2021-11-04T21:25:24Z)
• Rethinking InfoNCE: How Many Negative Samples Do You Need? [54.146208195806636]
  We study how many negative samples are optimal for InfoNCE in different scenarios via a semi-quantitative theoretical framework. We estimate the optimal negative sampling ratio using the $K$ value that maximizes the training effectiveness function.
  arXiv  Detail & Related papers  (2021-05-27T08:38:29Z)
• Contrastive Attraction and Contrastive Repulsion for Representation Learning [131.72147978462348]
  Contrastive learning (CL) methods learn data representations in a self-supervision manner, where the encoder contrasts each positive sample over multiple negative samples. Recent CL methods have achieved promising results when pretrained on large-scale datasets, such as ImageNet. We propose a doubly CL strategy that separately compares positive and negative samples within their own groups, and then proceeds with a contrast between positive and negative groups.
  arXiv  Detail & Related papers  (2021-05-08T17:25:08Z)
• Doubly Contrastive Deep Clustering [135.7001508427597]
  We present a novel Doubly Contrastive Deep Clustering (DCDC) framework, which constructs contrastive loss over both sample and class views. Specifically, for the sample view, we set the class distribution of the original sample and its augmented version as positive sample pairs. For the class view, we build the positive and negative pairs from the sample distribution of the class. In this way, two contrastive losses successfully constrain the clustering results of mini-batch samples in both sample and class level.
  arXiv  Detail & Related papers  (2021-03-09T15:15:32Z)
• Structure Aware Negative Sampling in Knowledge Graphs [18.885368822313254]
  A crucial aspect of contrastive learning approaches is the choice of corruption distribution that generates hard negative samples. We propose Structure Aware Negative Sampling (SANS), an inexpensive negative sampling strategy that utilizes the rich graph structure by selecting negative samples from a node's k-hop neighborhood.
  arXiv  Detail & Related papers  (2020-09-23T19:57:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.