Diffusion-based Negative Sampling on Graphs for Link Prediction

• URL: http://arxiv.org/abs/2403.17259v1
• Date: Mon, 25 Mar 2024 23:07:31 GMT
• Title: Diffusion-based Negative Sampling on Graphs for Link Prediction
• Authors: Trung-Kien Nguyen, Yuan Fang,
• Abstract summary: 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.
• Score: 8.691564173331924
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Link prediction is a fundamental task for graph analysis with important applications on the Web, such as social network analysis and recommendation systems, etc. Modern graph link prediction methods often employ a contrastive approach to learn robust node representations, where negative sampling is pivotal. Typical negative sampling methods aim to retrieve hard examples based on either predefined heuristics or automatic adversarial approaches, which might be inflexible or difficult to control. Furthermore, in the context of link prediction, most previous methods sample negative nodes from existing substructures of the graph, missing out on potentially more optimal samples in the latent space. To address these issues, we investigate 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 and reconcile them for effective graph link prediction. We further demonstrate that DMNS follows the sub-linear positivity principle for robust negative sampling. Extensive experiments on several benchmark datasets demonstrate the effectiveness of DMNS.

Related papers

• Contrastive CFG: Improving CFG in Diffusion Models by Contrasting Positive and Negative Concepts [55.298031232672734]
  As-Free Guidance (CFG) has proven effective in conditional diffusion model sampling for improved condition alignment. We present a novel method to enhance negative CFG guidance using contrastive loss.
  arXiv  Detail & Related papers  (2024-11-26T03:29:27Z)
• Enhancing Link Prediction with Fuzzy Graph Attention Networks and Dynamic Negative Sampling [0.0]
  Fuzzy Graph Attention Networks (FGAT) is a novel approach integrating fuzzy rough sets for dynamic negative sampling. FNS selects high-quality negative edges based on fuzzy similarities, improving training efficiency. Experiments on two research collaboration networks demonstrate FGAT's superior link prediction accuracy, outperforming state-of-the-art baselines.
  arXiv  Detail & Related papers  (2024-11-12T02:08:19Z)
• Layer-diverse Negative Sampling for Graph Neural Networks [19.84639875144519]
  Graph neural networks (GNNs) are a powerful solution for various structure learning applications. We propose a layer-diverse negative sampling method for message-passing propagation. We demonstrate the effectiveness of our approach in improving the diversity of negative samples and overall learning performance.
  arXiv  Detail & Related papers  (2024-03-18T01:48:50Z)
• Graph Out-of-Distribution Generalization with Controllable Data Augmentation [51.17476258673232]
  Graph Neural Network (GNN) has demonstrated extraordinary performance in classifying graph properties. Due to the selection bias of training and testing data, distribution deviation is widespread. We propose OOD calibration to measure the distribution deviation of virtual samples.
  arXiv  Detail & Related papers  (2023-08-16T13:10:27Z)
• Your Negative May not Be True Negative: Boosting Image-Text Matching with False Negative Elimination [62.18768931714238]
  We propose a novel False Negative Elimination (FNE) strategy to select negatives via sampling. The results demonstrate the superiority of our proposed false negative elimination strategy.
  arXiv  Detail & Related papers  (2023-08-08T16:31:43Z)
• Energy-based Out-of-Distribution Detection for Graph Neural Networks [76.0242218180483]
  We propose a simple, powerful and efficient OOD detection model for GNN-based learning on graphs, which we call GNNSafe. GNNSafe achieves up to $17.0%$ AUROC improvement over state-of-the-arts and it could serve as simple yet strong baselines in such an under-developed area.
  arXiv  Detail & Related papers  (2023-02-06T16:38:43Z)
• Relation-aware Graph Attention Model With Adaptive Self-adversarial Training [29.240686573485718]
  This paper describes an end-to-end solution for the relationship prediction task in heterogeneous, multi-relational graphs. We particularly address two building blocks in the pipeline, namely heterogeneous graph representation learning and negative sampling. We introduce a parameter-free negative sampling technique -- adaptive self-adversarial (ASA) negative sampling.
  arXiv  Detail & Related papers  (2021-02-14T16:11:56Z)
• 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)
• Understanding Negative Sampling in Graph Representation Learning [87.35038268508414]
  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.
  arXiv  Detail & Related papers  (2020-05-20T06:25:21Z)
• Reinforced Negative Sampling over Knowledge Graph for Recommendation [106.07209348727564]
  We develop a new negative sampling model, Knowledge Graph Policy Network (kgPolicy), which works as a reinforcement learning agent to explore high-quality negatives. kgPolicy navigates from the target positive interaction, adaptively receives knowledge-aware negative signals, and ultimately yields a potential negative item to train the recommender.
  arXiv  Detail & Related papers  (2020-03-12T12:44:30Z)

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.